在这里只提供模板。
一维情形
提供区间和功能，支援单点delta更新。sum得到的是[1,pos]的值的和。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
#pragma mark - Binary Indexed Tree (BIT) 1D //index begins from ONE //init:memset BIT,set BIT_size int BIT[MAXN];//container,may need to adjust MAXN or type.assuming the index won't overflow int int BIT_size;//should assign when use inline int lowbit(int a){ return a & (-a); } void BIT_modify(int pos,int delta){//type of delta may need to modify for (int x = pos; x <= BIT_size; x += lowbit(x)) { BIT[x] += delta; } } int BIT_sum(int pos){//return type may alter int ret = 0; for (int x = pos; x > 0; x -= lowbit(x)) { ret += BIT[x]; } return ret; } #pragma mark - |
二维情形
提供矩阵和功能，支援单点更新，sum得到的是从(1,1)拉到(posi,posj)的矩阵中数的总和。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
#pragma mark - Binary Indexed Tree (BIT) 2D //index begins from ONE //init:memset BIT,set BIT_size int BIT[MAXR][MAXC];//container,may need to adjust MAXN or type.assuming the index won't overflow int int BIT_Rsize;//number of rows int BIT_Csize[MAXC];//number of columns inline int lowbit(int a){ return a & (-a); } void BIT_modify(int posi,int posj,int delta){//type of delta may need to modify for (int x = posi; x <= BIT_Rsize; x += lowbit(x)) { for (int y = posj; y <= BIT_Csize[y]; y += lowbit(y)) { BIT[x][y] += delta; } } } int BIT_sum(int posi,int posj){//return type may alter int ret = 0; for (int x = posi; x > 0; x -= lowbit(x)) { for (int y = posj; y > 0; y -= lowbit(x)) { ret += BIT[x][y]; } } return ret; } #pragma mark - |
