又是长期没刷题的咸鱼今天做了道树状数组的题。这道题一开始我没想用二维的想着用一维的树状数组把二维下标重新排列成一维的比如(x*ny1)。但后来发现这样不行会多算比如4×4的矩阵下标0≤x≤30≤y≤3对应一维下标从1对应到161 2 3 45 6 7 89 10 11 1213 14 15 16若查找范围是(1,1)-6 到(2,3)-12 这个矩阵范围此种方法会把9位置上的数也算上。所以用二维数组。AC代码如下#includecstdio #includecstring #includeiostream #includealgorithm using namespace std; const int INF0x3f3f3f3f; #define ll long long const int MAX1030; int n; ll c[MAX][MAX]; int lowbit(int x) { return x(-x); } void update(int x,int y,int val) { for(int ix;in;ilowbit(i)) for(int jy;jn;jlowbit(j)) c[i][j]val; } ll quary(int x,int y) { ll ans0; for(int ix;i0;i-lowbit(i)) for(int jy;j0;j-lowbit(j)) ansc[i][j]; return ans; } int main() { int ins; while(scanf(%d,ins)1) { if(ins3) break; else if(ins0) { scanf(%d,n); memset(c,0,sizeof(c)); continue; } else if(ins1) { int x,y,t; scanf(%d%d%d,x,y,t); x;y; update(x,y,t); } else if(ins2) { int l,b,r,t; scanf(%d%d%d%d,l,b,r,t); l;b;r;t; printf(%d\n,quary(r,t)-quary(r,b-1)-quary(l-1,t)quary(l-1,b-1));//注意!!尤其是l-1,b-1 } } return 0; }
