树状数组

 lowbit 函数

inline int lowbit(int x) { return x & (-x); }

 单点修改

void update(int res, int plus)
{
	for (int i = res; i <= n; i += lowbit(i))
		c[i] += plus;
}

 区间求和

int sum(int end)
{
	int res = 0;
	for (int i = end; i; i -= lowbit(i))
		res += c[i];
	return res;
}

 初始化

int pre[maxn];
void init()
{
	for (int i = 1; i <= n; i++)
	{
		pre[i] = pre[i - 1] + a[i];
		c[i] = pre[i] - pre[i - lowbit(i)];
	}
}