树状数组

树状数组

• 区间查询，单点修改(主要求前缀和吧，改一改可以计数)
• 单点查询，区间修改(维护差分数组)
• 区间查询，区间修改(比较麻烦，两个树状数组维护)

区间查询(基础）

（看图）类似前缀和，(当成前缀和用)，但是为了减少单点修改复杂度写成树状的，每点更新时向上找“根”。
查询时找 \(lowbit\) (二进制中最右边的 \(1\) 和 右边的 \(0\) 组成的数)，见

二进制

void add(int x,int y)
{
	for(;x<=n;x+= (x&-x)) c[x]+=y;
}
int ask(int x)
{
	int ans=0;
	for(;x;x-=(x&-x)) ans+=c[x];
	return ans;
}
int main()
{
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		add(i,a[i]);
	}
	int x,y;
	scanf("%d%d",&x,&y);
	if()
		add(x,y);
	else
		printf("%d\n",ask(y)-ask(x-1));
	return 0;
}