树状数组工作原理详解

一维与二维树状数组对比

一维树状数组：

• 维护一维区间和
• 计算前缀和：统计1~x范围内的数值总和
• 单点更新和区间查询的时间复杂度均为O(log n)

二维树状数组：

• 维护二维平面和
• 计算矩形区域和：统计(1,1)到(x,y)矩形区域内的数值总和
• 单点更新和区域查询的时间复杂度均为O(log n · log n)
• 每个节点(x,y)管理的区域范围由lowbit(x)和lowbit(y)共同决定

二维树状数组的分治架构

1. 分层结构：

   • 首先沿X轴方向进行二分划分
   • 每个X区间再沿Y轴方向进行二分划分
   • 形成"树中树"的嵌套层次结构

2. 更新操作流程：

   def 更新(x, y, 增量):
       while x <= 最大X值:
           y临时 = y
           while y临时 <= 最大Y值:
               树状数组[x][y临时] += 增量
               y临时 += lowbit(y临时)
           x += lowbit(x)
   

   • 外层循环处理X维度（O(log n)时间）
   • 内层循环处理Y维度（O(log n)时间）
   • 总体时间复杂度：O(log² n)

3. 查询操作流程：

   def 查询(x, y):
       结果 = 0
       while x > 0:
           y临时 = y
           while y临时 > 0:
               结果 += 树状数组[x][y临时]
               y临时 -= lowbit(y临时)
           x -= lowbit(x)
       return 结果
   

   • 采用与更新操作类似的双层循环结构
   • 当向右子树查询时，需要累加左子树的值

实际应用场景

针对移动通信基站监控问题：

• 更新操作（类型1指令）：在坐标(x,y)处增加A部手机 更新基站数据(x坐标, y坐标, 新增手机数)

#include <cstring>
#include <cstdio>
using namespace std;
int tr[1500][1500], n;
int lowbit(int x){
	return x&(-x);
}
void updata(int x, int y, int a){
	for(int i=x; i<=n; i+=lowbit(i)){
		for(int j=y; j<=n; j+=lowbit(j)){
			tr[i][j]+=a;
		}
	}
}
int getsum(int x, int y){
	int s=0;
	for(int i=x; i>0; i-=lowbit(i)){
		for(int j=y; j>0; j-=lowbit(j)){
			s+=tr[i][j];
		}
	}
	return s;
}
int main(){
	int op, x, y, a, l, b, r, t;
	memset(tr, 0, sizeof(tr));
	scanf("%d%d", &op, &n);
	while(scanf("%d", &op)){
		if(op==3) break;
		if(op==1){
			scanf("%d%d%d", &x, &y, &a);
			updata(x+1, y+1, a);
		}
		if(op==2){
			scanf("%d%d%d%d", &l, &b, &r, &t);
			printf("%d\n", getsum(r+1, t+1)-getsum(l, t+1)-getsum(r+1, b)+getsum(l, b));
		}
	}
	return 0;
}