多维树状数组

多维树状数组,顾名思义,是树状数组在多维空间上的扩展.它可以动态维护多维空间的前序和.

意义

c[x,y,z,....]表示的是a[x-lowbit(x)+1,y-lowbit(y)+1,z-lowbit(z),....]到a[x,y,z,....]内的区间和.

操作

和一维树状数组类似

修改

复杂度O(log(n)^k)

void modify(int w,int x,int y,int z....)
{
	for(int x1=x;x1<=n;x1+=lowbit(x1))
		for(int x2=y;x2<=n;x2+=lowbit(x2))
			for(int x3=z;x3<=n;x3+=lowbit(x3))
				....
					c[x1][x2][x3][....]+=w;
	return ;
}

查询

O(log(n)^k)

long query(long x,long y,long z,....)
{
	long ans=0;
	for(int x1=x;x1>0;x1-=lowbit(x1))
		for(int x2=y;x2>0;x2-=lowbit(x2))
			for(int x3=z;x3>0;x3-=lowbit(x3))
				....
					ans+=c[x1][x2][x3][....];
	return ans;
}

查询区间(x,y)-(x1,y1)时,可根据容斥原理,调用query(x1,y1)-query(x-1,y1)-query(x1,y-1)+query(x-1,y-1);

参见

• 树状数组