基本介紹
- 中文名：二維樹狀數組
- 外文名：Two-dimensional binary indexed tree
- 領域：計算機科學
定義,推理過程,代碼,例題,問題,實現代碼如下,
定義
二維樹狀數組是在樹狀數組的基礎上拓展而來的一個由數字構成的大矩陣，能進行兩種操作對矩陣里的某個數加上一個整數（可正可負）或查詢某個子矩陣里所有數字的和，要求對每次查詢，輸出結果。一維樹狀數組很容易擴展到二維，在二維情況下:數組A[][]的樹狀數組定義為：
C[x][y] = ∑ a[i][j], x-lowbit(x) + 1 <= i <= x, y-lowbit(y) + 1 <= j <= y.
推理過程
設原始二維數組為： A[][]={{a11,a12,a13,a14,a15,a16,a17,a18,a19}, {a21,a22,a23,a24,a25,a26,a27,a28,a29}, {a31,a32,a33,a34,a35,a36,a37,a38,a39}， {a41,a42,a43,a44,a45,a46,a47,a48,a49}}; 記: B[1]={a11,a11+a12,a13,a11+a12+a13+a14,a15,a15+a16,...} 這是第一行的一維樹狀數組 B[2]={a21,a21+a22,a23,a21+a22+a23+a24,a25,a25+a26,...} 這是第二行的一維樹狀數組 B[3]={a31,a31+a32,a33,a31+a32+a33+a34,a35,a35+a36,...} 這是第三行的一維樹狀數組 B[4]={a41,a41+a42,a43,a41+a42+a43+a44,a45,a45+a46,...} 這是第四行的一維樹狀數組 於是有：C[1][1]=a11,C[1][2]=a11+a12,C[1][3]=a13,C[1][4]=a11+a12+a13+a14,c[1][5]=a15,C[1][6]=a15+a16,... 這是A[][]第一行的一維樹狀數組 C[2][1]=a11+a21,C[2][2]=a11+a12+a21+a22,C[2][3]=a13+a23,C[2][4]=a11+a12+a13+a14+a21+a22+a23+a24, C[2][5]=a15+a25,C[2][6]=a15+a16+a25+a26,... 這是A[][]數組第一行與第二行相加後的樹狀數組 C[3][1]=a31,C[3][2]=a31+a32,C[3][3]=a33,C[3][4]=a31+a32+a33+a34,C[3][5]=a35,C[3][6]=a35+a36,... 這是A[][]第三行的一維樹狀數組 C[4][1]=a11+a21+a31+a41,C[4][2]=a11+a12+a21+a22+a31+a32+a41+a42,C[4][3]=a13+a23+a33+a43,... 這是A[][]數組第一行+第二行+第三行+第四行後的樹狀數組 代碼
在二維情況下，如果修改了A[i][j]=delta,則對應的二維樹狀數組更新函式為：
void Modify(int i, int j, int delta){ A[i][j]+=delta; for(int x = i; x< A.length; x += lowbit(x)) for(int y = j; y <A[i].length; y += lowbit(y)) C[x][y] += delta;}在二維情況下，求子矩陣元素之和∑ a[i][j](前i行和前j列)的函式為
int Sum(int i, int j){ int result = 0; for(int x = i; x > 0; x -= lowbit(x)) { for(int y = j; y > 0; y -= lowbit(y)) { result += C[x][y]; } } return result;}Sun(1,1)=C[1][1];Sun(1,2)=C[1][2];Sun(1,3)=C[1][3]+C[1][2];...Sun(2,1)=C[2][1];Sun(2,2)=C[2][2];Sun(2,3)=C[2][3]+C[2][2];...Sun(3,1)=C[3][1]+C[2][1];Sun(3,2)=C[3][2]+C[2][2];其餘函式為：
int lowbit(int x){ return x&-x；}例題
問題
給定一個n×n矩陣A，它的元素是0或1。A[ i ][ j 意味著第i行j列的數值。最初我們有A[ i ][ j ]= 0（1 < = i，j = n）。
我們可以用下列方式改變矩陣。給定一個矩形的左上角是（X1，Y1），右下角是（x2，y2），我們改變矩形的所有元素的使用“not”操作（如果它是一個“0”，然後把它換成“1”，否則換成“0”）。為了維護矩陣的信息，你被要求編寫一個程式來接收和執行兩種指令。
1.C x1 y1 x2 y2（1<= X1<=X2<=N，1<=Y1<=Y2<=N）
通過左上角為（x1，y1）,右下角為（x2，y2）的矩形來改變矩陣的值
即將這個矩形範圍內的值全部取反
2.Q x y（1≤x，y≤n）查詢A[ x ][ y ]
Sample Input 12 10C 2 1 2 2Q 2 2C 2 1 2 1Q 1 1C 1 1 2 1C 1 2 1 2C 1 1 2 2Q 1 1C 1 1 2 1Q 2 1Sample Output 1001
實現代碼如下
C++：
#include <iostream>#include <stdio.h>#include <string.h>#include <string>#include <stack>#include <queue>#include <map>#include <set>#include <vector>#include <math.h>#include <bitset>#include <list>#include <algorithm>#include <climits>using namespace std;#define lson 2*i#define rson 2*i+1#define LS l,mid,lson#define RS mid+1,r,rson#define UP(i,x,y) for(i=x;i<=y;i++)#define DOWN(i,x,y) for(i=x;i>=y;i--)#define MEM(a,x) memset(a,x,sizeof(a))#define W(a) while(a)#define gcd(a,b) __gcd(a,b)#define LL long long#define N 1005#define INF 0x3f3f3f3f#define EXP 1e-8#define lowbit(x) (x&-x)const int mod = 1e9+7;int c[N][N],n,m,cnt,s,t;int a[N][N];int sum(int x,int y){ int ret = 0; int i,j; for(i = x; i>=1; i-=lowbit(i)) { for(j = y; j>=1; j-=lowbit(j)) { ret+=c[i][j]; } } return ret;}void add(int x,int y){ int i,j; for(i = x; i<=n; i+=lowbit(i)) { for(j = y; j<=n; j+=lowbit(j)) { c[i][j]++; } }}int main(){ int i,j,x,y,ans,t; int x1,x2,y1,y2; char op[10]; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); MEM(c,0); MEM(a,0); while(m--) { scanf("%s",op); if(op[0]=='C') { scanf("%d%d%d%d",&x1,&y1,&x2,&y2); x1++,y1++,x2++,y2++; add(x2,y2); add(x1-1,y1-1); add(x2,y1-1); add(x1-1,y2); } else { scanf("%d%d",&x1,&y1); x2 = x1,y2 = y1; x1++,y1++,x2++,y2++; printf("%d\n",sum(x1,y1)); } } printf("\n"); } return 0;}Pascal：
var n,k,i,j,t:longint; ch:char; c:array[0..1000,0..1000] of longint;procedure add(x,y:longint);var i,j:longint;begin i:=x; while i<=n do begin j:=y; while j<=n do begin inc(c[i,j]); j:=j+j and (-j); end; i:=i+i and (-i); end;end;procedure qc;var x1,x2,y1,y2:longint;begin readln(x1,y1,x2,y2); add(x1,y1); add(x1,y2+1); add(x2+1,y1); add(x2+1,y2+1);end;function sum(x,y:longint):longint;var v:longint; i,j:longint;begin v:=0; i:=x; while i>0 do begin j:=y; while j>0 do begin v:=v+c[i,j]; j:=j-j and (-j); end; i:=i-i and (-i); end; exit(v);end;procedure qq;var x,y:longint;begin readln(x,y); writeln(sum(x,y) mod 2);end;begin readln(k); for i:=1 to k do begin fillchar(c,sizeof(c),0); readln(n,t); for j:=1 to t do begin read(ch); if ch='C' then qc else qq; end; writeln; end;end.
