树状数组

一维

核心函数

#define lowbit(x) ((x)&(-x))
int tr[N];
void add(int x,int v)
{
    for(int i = x; i <= n; i += lowbit(i)) tr[i] += v;
}
int query(int x)
{
    int res = 0;
    for(int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}

单点更新 区间查询

#include <iostream>
#include <cstdio>
#define lowbit(x) ((x)&(-x))
using namespace std;
const int N = 100010;
int n, m;
int  a[N], tr[N];
void add(int x,int v)
{
    for(int i = x; i <= n; i += lowbit(i)) tr[i] += v;
}
int query(int x)
{
    int res = 0;
    for(int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}
int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++) add(i, a[i]);
    while(m--)
    {
        int l, r;
        scanf("%d %d", &l, &r);
        cout << query(r) - query(l - 1) << endl;
    }
    return 0;
}

区间更新 单点查询

#include <iostream>
#include <cstdio>
#define lowbit(x) ((x)&(-x))
using namespace std;
const int N = 100010;
int n, m;
int a[N], tr[N];
void add(int x,int v)
{
    for(int i = x; i <= n; i += lowbit(i)) tr[i] += v;
}
int query(int x)
{
    int res = 0;
    for(int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}
void insert(int l, int r, int v) 
{
    add(l,v); 
    add(r+1,-v);     
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) insert(i, i, a[i]);
    while(m--)
    {
        int l, r, k;
        cin >> l >> r >> k;
        insert(l, r, k);
    }
    for(int i = 1; i <=n; i++)
    {
        cout << query(i) << " ";
    }
    return 0;
}

区间更新 区间查询

#include <iostream>
#include <cstdio>
#define lowbit(x) ((x)&(-x))
using namespace std;
const int N =100010;
int n, m;
int a[N, tr1[N], tr2[N];
void add(int x, int v)
{
    for(int i = x; i <= n; i+=lowbit(i))
    {
        tr1[i] += v;
        tr2[i] += v * (x - 1);
    }
}
int querySum(int x)
{
    int res = 0;
    for(int i = x; i; i-=lowbit(i))
        res += x * tr1[i] - tr2[i];
    return res;
}
int queryNum(int x)
{ 
    int res = 0;
    for(int i = x; i; i-=lowbit(i))
        res += tr1[i];
    return res;
}
void insert(int l, int r, int v)
{
    add(l, v);
    add(r+1,-v);
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) insert(i, i, a[i]);
    while(m--)
    {
        int l, r;
        scanf("%d %d", &l, &r);
        cout << querySum(r) - querySum(l - 1) << endl;
    }
    return 0;
}

#include <iostream>
#include <cstdio>
#define lowbit(x) ((x)&(-x))
using namespace std;
const int N =100010;
int n, m;
int a[N];
int tr1[N]; 
int tr2[N];
void add(int x, int v)
{
    for(int i = x; i <= n; i+=lowbit(i))
    {
        tr1[i] += v;
        tr2[i] += v * (x - 1);
    }
}
int querySum(int x)
{
    int res = 0;
    for(int i = x; i; i-=lowbit(i))
        res += x * tr1[i] - tr2[i];
    return res;
}
int queryNum(int x)
{ 
    int res = 0;
    for(int i = x; i; i-=lowbit(i))
        res += tr1[i];
    return res;
}
void insert(int l, int r, int v)
{
    add(l, v);
    add(r+1,-v);
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) insert(i, i, a[i]);
    while(m--)
    {
        int l, r, k;
        cin >> l >> r >> k;
        insert(l, r, k);
    }
    for(int i = 1; i <=n; i++)
    {
        cout << queryNum(i) << " ";
    }
    return 0;
}

二维

核心函数

#define lowbit(x) ((x)&(-x))
int tr[N][M];
void add(int x,int y,int v)
{  
    for(int i = x; i <= n; i+=lowbit(i))
        for(int j = y; j <= m; j+=lowbit(j))
            tr[i][j] += v;
}
int query(int x,int y)
{  
    int result = 0;  
    for(int i = x; i; i-=lowbit(i))
        for(int j = y; j; j-=lowbit(j))
            result += tr[i][j];
    return result;  
} 

单点更新 区间查询

#include <iostream>
#include <cstdio>
#define lowbit(x) ((x)&(-x))
using namespace std;
const int N = 1010, M = 1010;
int a[N][M], tr[N][M];
int n, m, q;
void add(int x,int y,int v)
{  
    for(int i = x; i <= n; i+=lowbit(i))
        for(int j = y; j <= m; j+=lowbit(j))
            tr[i][j] += v;
}
int query(int x,int y)
{  
    int result = 0;  
    for(int i = x; i; i-=lowbit(i))
        for(int j = y; j; j-=lowbit(j))
            result += tr[i][j];
    return result;  
} 
int main()
{
    cin >> n >> m >> q;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            scanf("%d", &a[i][j]);  
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            add(i, j, a[i][j]);
    while(q--)
    {
        int x1, y1, x2, y2;
        scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
        cout << query(x2,y2) - query(x1-1, y2) - query(x2, y1 - 1) + query(x1-1, y1 -1) << endl;
    }
    return 0;
}

区间更新 单点查询

#include <iostream>
#include <cstdio>
#define lowbit(x) ((x)&(-x))
using namespace std;
const int N = 1010, M = 1010;
int a[N][M], tr[N][M];
int n, m, q;
void add(int x,int y,int v)
{  
    for(int i = x; i <= n; i+=lowbit(i))
        for(int j = y; j <= m; j+=lowbit(j))
            tr[i][j] += v;
}
int query(int x,int y)
{  
    int result = 0;  
    for(int i = x; i; i-=lowbit(i))
        for(int j = y; j; j-=lowbit(j))
            result += tr[i][j];
    return result;  
} 
void insert(int x1,int y1,int x2,int y2,int v)
{
    add(x1,y1,v);
    add(x2+1,y1,-v);
    add(x1,y2+1,-v);
    add(x2+1,y2+1,v);
}
int main()
{
    cin >> n >> m >> q;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            scanf("%d", &a[i][j]);    
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            insert(i,j,i,j,a[i][j]); 
    while(q--)
    {
        int x1, y1, x2, y2, v;
        scanf("%d %d %d %d %d", &x1, &y1, &x2, &y2, &v);
        insert(x1, y1, x2, y2, v);
    }
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
            cout << query(i, j) << " ";
        cout << endl;
    }
    return 0;
}

区间更新 区间查询

#include <iostream>
#include <cstdio>
#define lowbit(x) ((x)&(-x))
using namespace std;
const int N = 1010, M = 1010;
int a[N][M], tr1[N][M], tr2[N][M], tr3[N][M], tr4[N][M];
int n, m, q;
void add(int x,int y,int v)
{  
    for(int i = x; i <= n; i+=lowbit(i))
        for(int j = y; j <= m; j+=lowbit(j))
        {
            tr1[i][j] += v;
            tr2[i][j] += v * (x-1);
            tr3[i][j] += v * (y-1);
            tr4[i][j] += v * (x-1) * (y-1);
        }
}
int queryNum(int x,int y)
{  
    int result = 0;  
    for(int i = x; i; i-=lowbit(i))
        for(int j = y; j; j-=lowbit(j))
            result += tr1[i][j];
    return result;  
} 

int querySum(int x, int y)
{
    int res = 0;
    for(int i = x; i; i-=lowbit(i))
        for(int j = y; j; j-=lowbit(j))
            res += x * y * tr1[i][j] - y * tr2[i][j] - x * tr3[i][j] + tr4[i][j];
    return res;
}
void insert(int x1,int y1,int x2,int y2,int v)
{
    add(x1,y1,v);
    add(x2+1,y1,-v);
    add(x1,y2+1,-v);
    add(x2+1,y2+1,v);
}
int main()
{
    cin >> n >> m >> q;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            scanf("%d", &a[i][j]);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            insert(i,j,i,j,a[i][j]); 
    while(q--)
    {
        int x1, y1, x2, y2;
        scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
        cout << querySum(x2,y2) - querySum(x1-1, y2) - querySum(x2, y1 - 1) + querySum(x1-1, y1 -1) << endl;
    }
    return 0;
}

#include <iostream>
#include <cstdio>
#define lowbit(x) ((x)&(-x))
using namespace std;
const int N = 1010, M = 1010;
int a[N][M], tr1[N][M], tr2[N][M], tr3[N][M], tr4[N][M];
int n, m, q;
void add(int x,int y,int v)
{  
    for(int i = x; i <= n; i+=lowbit(i))
        for(int j = y; j <= m; j+=lowbit(j))
        {
            tr1[i][j] += v;
            tr2[i][j] += v * (x-1);
            tr3[i][j] += v * (y-1);
            tr4[i][j] += v * (x-1) * (y-1);
        }
}
int queryNum(int x,int y)
{  
    int result = 0;  
    for(int i = x; i; i-=lowbit(i))
        for(int j = y; j; j-=lowbit(j))
            result += tr1[i][j];
    return result;  
} 

int querySum(int x, int y)
{
    int res = 0;
    for(int i = x; i; i-=lowbit(i))
        for(int j = y; j; j-=lowbit(j))
            res += x * y * tr1[i][j] - y * tr2[i][j] - x * tr3[i][j] + tr4[i][j];
    return res;
}
void insert(int x1,int y1,int x2,int y2,int v)
{
    add(x1,y1,v);
    add(x2+1,y1,-v);
    add(x1,y2+1,-v);
    add(x2+1,y2+1,v);
}
int main()
{
    cin >> n >> m >> q;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            scanf("%d", &a[i][j]);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            insert(i,j,i,j,a[i][j]); 
    while(q--)
    {
        int x1, y1, x2, y2, v;
        scanf("%d %d %d %d %d", &x1, &y1, &x2, &y2, &v);
        insert(x1, y1, x2, y2, v);
    }
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
            cout << queryNum(i, j) << " ";
        cout << endl;
    }
    return 0;
}