一维二维树状数组模板

树状数组也可说是二分索引树，是一种高级数据结构，但其实用起来很方便。

本文参考博客如下：

http://www.cppblog.com/menjitianya/archive/2015/11/02/212171.html

https://blog.csdn.net/zars19/article/details/54620021

https://www.cnblogs.com/RabbitHu/p/BIT.html

1、单点修改+区间查询

int c[maxn];
int lowbit(int x)//获取最低位1 
{
    return x&(-x);
}
void update(int x,int c)//单点更新 
{
    for(int i=x;i<=n;i+=lowbit(i))
    {
        c[i]+=c;
     } 
}
int query(int x)//查询前缀和 c[1...x] 
{
    int ans=0;
    for(int i=x;i>=0;i-=lowbit(i))
    {
        ans+=c[i];
    }
    return ans;
}
int rgquery(int l,int r)//区间查询 
{
    return query(r)-query(l-1); 
 }

View Code

2、区间修改+单点查询

 1 int c1[maxn];//拆分数列 
 2 void updata(int x,int y) //a[x-n]区间修改 
 3 {
 4     for(int i=x;i<=n;i+=lowbit(i))
 5     {
 6         c1[i]+=y;
 7     }
 8 }
 9 void range_updata(int l,int r,int val)
10 {
11     updata(l,val);
12     updata(r+1,-val);
13 }
14 
15 int query(int x)
16 {
17     int ans=0;
18     for(int i=x;i;i-=lowbit(i))
19     {
20         ans+=c1[i];
21     }
22     return ans;
23 }

View Code

3、区间修改+区间查询

 1 void add(ll p, ll x){
 2     for(int i = p; i <= n; i += i & -i)
 3         sum1[i] += x, sum2[i] += x * p;
 4 }
 5 void range_add(ll l, ll r, ll x){
 6     add(l, x), add(r + 1, -x);
 7 }
 8 ll ask(ll p){
 9     ll res = 0;
10     for(int i = p; i; i -= i & -i)
11         res += (p + 1) * sum1[i] - sum2[i];
12     return res;
13 }
14 ll range_ask(ll l, ll r){
15     return ask(r) - ask(l - 1);
16 }

二维树状数组

在一维树状数组中，tree[x]（树状数组中的那个“数组”）记录的是右端点为x、长度为lowbit(x)的区间的区间和。
那么在二维树状数组中，可以类似地定义tree[x][y]记录的是右下角为(x, y)，高为lowbit(x), 宽为 lowbit(y)的区间的区间和。

1、单点修改+区间查询

void add(int x, int y, int z){ //将点(x, y)加上z
    int memo_y = y;
    while(x <= n){
        y = memo_y;
        while(y <= n)
            tree[x][y] += z, y += y & -y;
        x += x & -x;
    }
}
void ask(int x, int y){//求左上角为(1,1)右下角为(x,y) 的矩阵和
    int res = 0, memo_y = y;
    while(x){
        y = memo_y;
        while(y)
            res += tree[x][y], y -= y & -y;
        x -= x & -x;
    }
}

2、区间修改+单点查询

void add(int x, int y, int z){ 
    int memo_y = y;
    while(x <= n){
        y = memo_y;
        while(y <= n)
            tree[x][y] += z, y += y & -y;
        x += x & -x;
    }
}
void range_add(int xa, int ya, int xb, int yb, int z){
    add(xa, ya, z);
    add(xa, yb + 1, -z);
    add(xb + 1, ya, -z);
    add(xb + 1, yb + 1, z);
}
void ask(int x, int y){
    int res = 0, memo_y = y;
    while(x){
        y = memo_y;
        while(y)
            res += tree[x][y], y -= y & -y;
        x -= x & -x;
    }
}

3、区间修改+区间查询

 1 const int N = 205;
 2 ll n, m, Q;
 3 ll t1[N][N], t2[N][N], t3[N][N], t4[N][N];
 4 void add(ll x, ll y, ll z){
 5     for(int X = x; X <= n; X += X & -X)
 6         for(int Y = y; Y <= m; Y += Y & -Y){
 7             t1[X][Y] += z;
 8             t2[X][Y] += z * x;
 9             t3[X][Y] += z * y;
10             t4[X][Y] += z * x * y;
11         }
12 }
13 void range_add(ll xa, ll ya, ll xb, ll yb, ll z){ //(xa, ya) 到 (xb, yb) 的矩形
14     add(xa, ya, z);
15     add(xa, yb + 1, -z);
16     add(xb + 1, ya, -z);
17     add(xb + 1, yb + 1, z);
18 }
19 ll ask(ll x, ll y){
20     ll res = 0;
21     for(int i = x; i; i -= i & -i)
22         for(int j = y; j; j -= j & -j)
23             res += (x + 1) * (y + 1) * t1[i][j]
24                 - (y + 1) * t2[i][j]
25                 - (x + 1) * t3[i][j]
26                 + t4[i][j];
27     return res;
28 }
29 ll range_ask(ll xa, ll ya, ll xb, ll yb){
30     return ask(xb, yb) - ask(xb, ya - 1) - ask(xa - 1, yb) + ask(xa - 1, ya - 1);
31 }