前几题运用了树状数组的 单点修改+区间查询,一维区间修改+单点查询(差分法),二维区间修改+单点查询(差分法)
这些都是树状数组的常规操作
树状数组还可以通过维护两个数组实现一维的区间修改+区间查询,详见:https://www.cnblogs.com/lcf-2000/p/5866170.html
但是二维的区间修改+区间查询很不好实现,这时不如直接用线段树实现
题目:
有一块有100*100个的格子的板子如下图。左上角的格子是(1,1),右下角的格子是(100,100) 我们可以对这个板子有三种不同的命令: 1. WHITE x, y, L // 在板子上画一个白方块, //)方块的左上角是(x,y) // 右下角是 (x+L-1, y+L-1) 2. BLACK x, y, L // 在板子上画一个黑方块 // 方块的左上角是 (x, y) // 右下角是 (x+L-1, y+L-1) 3. TEST x, y, L // 询问方块(x,y)到(x+L-1,y+L-1)中黑色方块的数量 开始的时候,板子上的方块都是白色的。 我们对板子进行一系列的操作。你的任务就是写一个程序,计算出指定区域的黑块的数量。
注意题目描述虽然是线段树或树状数组的套路,但数据范围较小(100*100),操作简单
这时侯就没必要用树状数组 ,看其他答案的树状数组区间修改依旧是逐点遍历实现的 ,这时候倒不如直接暴力
树状数组 修改O(nlog n) 查询O(log n)
暴力 修改 O(n)查询(n)
#include <cstdio> #include <cstring> using namespace std; // 这题数据很小,完全没必要用树状数组 // 而且二维树状数组区间修改+区间查询的操作 我也不会 int pic[105][105]; int main( ){ int n; char op[10]; int ans; int x,y,l; scanf("%d" ,&n); while( n--){ scanf("%s",op); if( op[0]=='B'){ scanf("%d%d%d" ,&x ,&y ,&l); for( int i=x ; i<x+l ;i++) for( int j=y ; j<y+l ;j++){ if( pic[i][j] == 0)pic[i][j]++; } } if( op[0]=='W'){ scanf("%d%d%d" ,&x ,&y ,&l); for( int i=x ; i<x+l ;i++) for( int j=y ; j<y+l ;j++){ if( pic[i][j] == 1)pic[i][j]--; } } if( op[0]=='T'){ ans=0; scanf("%d%d%d" ,&x ,&y ,&l); for( int i=x ; i<x+l ;i++) for( int j=y ; j<y+l ;j++){ ans+=pic[i][j]; } printf("%d\n" ,ans); } } return 0; }