浅谈树状数组

概念：

定义：

树状数组是一种结合了树的思想，常用来处理前缀问题（如前缀最大/最小值，前缀和）的一种数据结构，区查和单修时间复杂度都为 $\log (n)$。

（右图括号中的值表示原序列中该数的值，未打括号的表示下标）

这一张图可以很好地展示一维树状数组的结构及其维护信息的原理。令该树状数组为 $bit$，$c$ 为数组的前缀和，容易发现，$$c[1]=bit[1]$$ $$c[2]=bit[2]$$$$c[3]=bit[2]+bit[3]...$$ $$c[7]=bit[7]+bit[6]+bit[4]$$。

结合图观察，通过树状数组求前缀和就是将某个区间拆成树状数组里的若干段的规律就是将该数进行二进制拆分，每一次取出 $01$ 串中最靠右的 $1$ 表示的数作为树状数组中的下标，然后加起来即可。
例如 $A[5]$，以二进制表示就是 $A[0101]$ 拆分过后就是 $bit[0100]\mathrm{和}bit[0001]$，分别为 $bit[4]\mathrm{和}bit[1]$ 因此 $A[5]=bit[4]+bit[1]$。

lowbit：

那么如何每次准确地取出 $01$ 串中最靠右的一个 $1$ 呢？这里需要对当前数取负后再与上当前数即可。
在计算机中，负数用补码表示，补码等于正数用二进制表示后每一位取反后再加一。如 $5$ 用二进制表示就是 $0101$，那么 $-5$ 用二进制表示就是 $0101$ 按位取反，得到 $1010$，然后加一有 $1011$，这就是 $-5$的二进制表示法。为了取出最后一位 $1$，还应该将这个数与 $5$ 进行与运算，得到 $0001$，这样就顺利取出了 $01$ 串中的最后一位 $1$。在树状数组的实现中，我们常用这样一个 $lowbit$ 函数实现这样的操作：

int lowbit(int i){
	return i & -i;
}

还可以采用异或实现 $lowbit$ 此处不展开叙述，读者自行探索。

一维树状数组：

单修区查：

单修：

仍然结合图像。

假如我们对原序列中第十一位进行修改，那么树状数组中，包含原序列第十一位的数的信息的所有结点都需要改变，这就像从第十一位拉一条水平方向的横线（如右图），被这条横线所切到的所有结点的值都要被改变（红圆标注）。在这种情况下，树状数组中下标为 $11,12,16$ 的结点都需要被改变。
观察三数，转化为二进制后分别为 $1011,1100,10000$，可以发现，每一个数都相当于前一个数在它最靠右的 $1$ 的位置加上 $1$ 后所得到的数。这里仍然要用到 $lowbit$
实现如下：

void add(int x,int y){//在下标为x的地方加上y
	for(int i = x; i <= n; i += lowbit(i)){
		bit[i] += y;
	}
}

区查：

按照介绍 $lowbit$ 时所介绍的求前缀和的思想进行编程：

int query(int x){
	int ans = 0;
	for(int i = x; i > 0; i -= lowbit(i)){
		ans += bit[i];
	}
	return ans;
}

求得前缀和，进行区间和查询也就易如反掌了。

区修单查：

区修：

对于树状数组的区间修改，要运用差分的思想，一个数组的差分数组和它的前缀和是互逆的。

a[6] = {0, 1, 2, 3, 4, 5};
cf[6] = {0, 1, 1, 1, 1, 1}; //cf[i] = a[i] - a[i - 1] 差分
qzh[6] = {0, 1, 3, 6, 10, 15}; //qzh[i] = qzh[i - 1] + a[i] 前缀和

cf_qzh[6] = {0, 1, 2, 3, 4, 5}; //差分数组的前缀和数组
qzh_cf[6] = {0, 1, 2, 3, 4, 5}; //前缀和数组的差分数组

容易发现，差分数组的前缀和就是原数组的数，前缀和的差分数组就是原数组。
而差分数组的区间修改是将 $cf[l]+k,cf[r+1]-k$ （设让 $[l,r]$ 里的每个数加上 $k$，$cf$ 为原数组的差分数组）
对于这道题，我们不再在原数组上建树状数组了，改在差分数组上建树状数组。

单查：

每次区间修改，就对 $cf[l]+k,cf[r+1]-k$ ，查询每个数，即求 $[1,x]$ 的前缀和。

void change(int l,int r,int x){//将l到r的数加上x
	add(l,x);
	add(r + 1,-x);
}

$query,add$ 函数不变。

区修区查：

区修：

同上。

区查：

这里就需要稍微推一下柿子了。设原序列为 $A$。

$$\sum _{l=1}^r\sum _{j=1}^{i}bit[j]$$

这个柿子的结果就是区间和。展开得到：

$$bit[1]+(bit[1]+bit[2])+(bit[1]+bit[2]+bit[3])+\cdots +(bit[1]+bit[2]+bit[3]+\cdots +bit[p])$$

$$r\ast bit[1]+(r-1)\ast bit[2]+(r-2)\ast bit[3]+\cdots +2\ast bit[r-1]+bit[r]$$

化简后得：

$$\sum _{i=1}^{r}bit[i]\ast r-\sum _{i=1}^{r}bit[i]\ast (i-1)$$

因此只需要维护两个前缀和，分别是 $bit[i]\mathrm{和}bit[i]\ast (i-1)$。

二维树状数组：

单修区查：

其实跟一维的大同小异，这里就放代码了：

void add(int x,int y,int z){
	for(int i = x; i <= n; i += lobit(i)){
		for(int j = y; j <= m; j += lowbit(j)){
			bit[i][j] += z;
		}
	}
}
int query(int x,int y){//左上端点为（1，1），右下端点为（x，y）的矩阵元素之和
	int ans = 0;
	for(int i = x; i > 0; i -= lowbit(i)){
		for(int j = y; j > 0; j -= lowbit(j)){
			ans += bit[i][j];
		}
		return ans;
	}
}

在进行区间矩阵求和时，还要运用到容斥定理，如下图（找别人薅的

大正方形减去两个小的长方形，加上小正方形即为红框区间内的答案。

int tot(int x1,int y1,int x2,int y2){
	int ans = 0;
	ans += add(x2,y2);
	ans -= add(x2,y1 - 1);
	ans -= add(x1 - 1,y2);
	ans += add(x1 - 1,y1 - 1);
	return ans;
}

区修单查：

区修：

一位的区修依赖差分数组，那么二维的区修就依赖差分矩阵。
有如下矩阵

0 0 0 0 0 
0 0 0 0 0 
0 0 0 0 0 
0 0 0 0 0
0 0 0 0 0

想进行区域修改，得到

0 0 0 0 0
0 x x x 0
0 x x x 0
0 x x x 0
0 0 0 0 0

那么在差分矩阵里，就应该是这样的

0 0 0 0 0
0 x 0 0 -x
0 0 0 0 0
0 0 0 0 0
0 -x 0 0 x

代码如下：

void change(int x1,int y1,int x2,int y2,int x){
	add(x1,y1,x);
	add(x1,y2 + 1,-x);
	add(x2 + 1,y1,-x);
	add(x2 + 1,y2 + 1,x);
}

单查：

如一维一样，统计前缀和即可。

区修区查：

区修：

同上。

区查：

令 $a$ 为差分矩阵，则有

$$sum=\sum _{i=1}^x\sum _{j=1}^y\sum _{ii=1}^i\sum _{jj=1}^{j}a[ii][jj]$$

类比一维树状数组，发现 $a[x][y]$ 出现了 $(x-i+1)\ast (y-j+1)$ 次。
所以可以化简，得到：

$$\sum _{i=1}^x\sum _{j=1}^{y}a[i][j]\ast (x+1)\ast (y+1)-\sum _{i=1}^x\sum _{j=1}^{y}a[i][j]\ast (x+1)\ast j-\sum _{i=1}^x\sum _{j=1}^{y}a[i][j]\ast (y+1)\ast i+\sum _{i=1}^x\sum _{j=1}^{y}a[i][j]\ast i\ast j$$

显而易见，需要维护 $a[i][j]、a[i][j]\ast j、a[i][j]\ast i、a[i][j]\ast i\ast j$

void add(int x, int y, int z) {
    for (int i = x; i <= n; i += lowbit(i))
        for (int j = y; j <= m; j += lowbit(j)) {
        	bit1[i][j] += z;
        	bit2[i][j] += (ll)x * z;
        	bit3[i][j] += (ll)y * z;
        	bit4[i][j] += (ll)x * y * z;
		}
}
void chanhe(int x1,int y1,int x2,int y2,int x){
	Update(x1, y1, x);
	Update(x2 + 1, y2 + 1, x);
	Update(x1, y2 + 1, -x);
    Update(x2 + 1, y1, -x);
}