树状数组系列模板

区间修改 O(n*logn)

1.单点修改，区间查询

类似题目：

1.清点人数：https://www.acwing.com/problem/content/1269/
题目：https://www.luogu.com.cn/problem/P3374

#include<iostream>

using namespace std;

#define lowbit(x) (x & (-x))
typedef long long ll;
const int N = 5E5 + 5;

ll tree[N];
int n, m;

inline void update(int i, int x){
    for(int pos = i; pos <= n; pos += lowbit(pos))  tree[pos] += x;
} 

inline ll query(int i){
    ll ans = 0;
    for(int pos = i; pos; pos -= lowbit(pos))   ans += tree[pos];
    return ans;
}

int main(){
    cin>>n>>m;
    for(int i = 1; i <= n; i ++ ){
        int x;
        cin>>x;
        update(i, x);
    }
    while(m -- ){
        char op[2];
        cin>>op;
        int x, y;
        cin>>x>>y;
        if(op[0] == '1')    update(x, y);
        else if(op[0] == '2')   cout<<query(y) - query(x - 1)<<'\n';
    }
    return 0;
}

2.区间修改，单点查询

题目：https://www.luogu.com.cn/problem/P3368

#include<iostream>

using namespace std;

#define lowbit(x) (x & (-x))
typedef long long ll;
const int N = 5E5 + 5;

ll tree[N];
int n, m;

inline void update(int i, int x){
    for(int pos = i; pos <= n; pos += lowbit(pos))  tree[pos] += x;
} 

inline ll query(int i){
    ll ans = 0;
    for(int pos = i; pos; pos -= lowbit(pos))   ans += tree[pos];
    return ans;
}

int main(){
    cin>>n>>m;
    for(int i = 1; i <= n; i ++ ){
        ll b;
        cin>>b;
        update(i, b);
        update(i + 1, -b);
    }
    while(m -- ){
        char op[2];
        cin>>op;
        int x, y, k;
        if(op[0] == '1'){
            cin>>x>>y>>k;
            update(x, k);
            update(y + 1, -k);
        }
        else if(op[0] == '2'){
            cin>>x;
            cout<<query(x)<<'\n';
        }
    }
    return 0;
}

3.区间修改，区间查询

题目：https://www.acwing.com/solution/content/69657/

#include<iostream>

using namespace std;

#define lowbit(x) x & (-x)
const int N = 1E5 + 5;
typedef long long ll;

int n, m;
ll tree[2][N]; //0表示di,1表示idi

void update(int pos, ll x, int f){
    for(int i = pos; i < N; i += lowbit(i)) tree[f][i] += x;
}

ll query(int pos, int f){
    ll ans = 0;
    for(int i = pos; i; i -= lowbit(i)) ans += tree[f][i];
    return ans;
}

ll get_res(int pos){
    return (pos + 1) * query(pos, 0) - query(pos, 1); 
}

int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++ ){
        ll x;
        scanf("%lld", &x);
        update(i, x, 0);
        update(i + 1, -x, 0);
        update(i, i * x, 1);
        update(i + 1, -(i + 1) * x, 1);
    }
    char op[2];
    while(m -- ){
        scanf("%s", op);
        if(op[0] == 'C'){
            int l, r, x;
            scanf("%d%d%d", &l, &r, &x);
            update(l, x, 0);
            update(r + 1, -x, 0);
            update(l, l * x, 1);
            update(r + 1, -(r + 1) * x, 1);
        }
        else if(op[0] == 'Q'){
            int l, r;
            scanf("%d%d", &l, &r);
            printf("%lld\n", get_res(r) - get_res(l - 1));
        }
    }
    return 0;
}

4.树状数组 + 二分

类似题目:

1.买票->https://www.acwing.com/problem/content/description/262/

题目：谜一样的牛：https://www.acwing.com/problem/content/245/

#include<iostream>

using namespace std;

#define lowbit(x) (x & (-x))
const int N = 1E5 + 5;
typedef long long ll;

ll tree[N];
int init[N];
int res[N];
int n;

inline void update(int i, int x){
    for(int pos = i; pos <= n; pos += lowbit(pos))  tree[pos] += x;
}

inline ll query(int i){
    ll ans = 0;
    for(int pos = i; pos; pos -= lowbit(pos))   ans += tree[pos];
    return ans;
}

int main(){
    cin>>n;
    update(1, 1);
    for(int i = 2; i <= n; i ++ ){
        cin>>init[i];
        update(i, 1);
    }
    for(int i = n; i; i -- ){
        int l = 1, r = n;
        while(l < r){
            int mid = l + r >> 1;
            if(query(mid) < init[i] + 1)    l = mid + 1;
            else    r = mid;
        }
        res[i] = r;
        update(r, -1);
    }
    for(int i = 1; i <= n; i ++ )   cout<<res[i]<<'\n';
    return 0;
}

5.二维树状数组维护前缀和

题目：打鼹鼠：https://www.acwing.com/problem/content/description/1271/

#include<iostream>

using namespace std;

const int N = 1025;
#define lowbit(x) (x & (-x))

int tree[N][N];

inline void update(int i, int j, int c){
    for(int x = i; x <= N; x += lowbit(x))
        for(int y = j; y <= N; y += lowbit(y))
    tree[x][y] += c;
}

int query(int i, int j){
    int ans = 0;
    for(int x = i; x; x -= lowbit(x))
        for(int y = j; y; y -= lowbit(y))
            ans += tree[x][y];
    return ans;
}

int main(){
    int n, op;
    cin>>n;
    while(cin>>op, op != 3){
        int x, y, xx, yy, k;
        if(op == 1){
            cin>>x>>y>>k;
            update(x + 1, y + 1, k);    //+1防止出现0
        }
        else if(op == 2){
            cin>>x>>y>>xx>>yy;
            x ++, xx ++, y ++, yy ++;   //++防止出现0
            cout<<query(xx, yy) - query(x - 1, yy) - query(xx, y - 1) + query(x - 1, y - 1)<<'\n';
        }
    }
    return 0;
}

习题1：楼兰图腾

题目：https://www.acwing.com/problem/content/description/243/

通过树状数组求前面比当前数小的数个数，进而求出前大，后小和后大。
V图腾 = qh * hh
^图腾 = ql * hl

#include<iostream>

using namespace std;

#define lowbit(x) (x & (-x))
const int N = 2E5 + 5;
typedef long long ll;

int n;
ll tree[N];
ll v1, v2;

struct Node{
    ll val;a
    int id;
}B[N];

inline void update(int i, int x){
    for(int pos = i; pos <= n; pos += lowbit(pos))  tree[pos] += x;
}

inline ll query(int i){
    ll ans = 0;
    for(int pos = i; pos; pos -= lowbit(pos))   ans += tree[pos];
    return ans;
}

int main(){
    cin>>n;    
    for(int i = 1; i <= n; i ++ ){
        cin>>B[i].val;
        B[i].id = i;
    }
    for(int i = 1; i <= n; i ++ ){
        ll ql = query(B[i].val);    //前面小的
        ll qh = B[i].id - 1 - ql;   //前面大的
        ll hl = B[i].val - 1 - ql;  //后面小的
        ll hh = n - ql - qh - hl - 1;    //后面大的
        v1 += qh * hh;
        v2 += ql * hl;
        update(B[i].val, 1);
    }
    printf("%lld %lld", v1, v2);
    return 0;
}

习题2：逆序对的数量

逆序对拓展题：https://www.acwing.com/problem/content/description/1217/

题目：https://www.acwing.com/problem/content/790/

#include<iostream>
#include<algorithm>

using namespace std;

#define lowbit(x) (x & (-x))
typedef long long ll;
const int N = 1E5 + 5;

typedef struct{
    int id;
    int value;
}init;

ll tree[N];
int A[N];   //离散化后的数组
init B[N];
ll sum;

bool cmp(init a, init b){
    if(a.value < b.value)  return true;
    if(a.value == b.value && a.id < b.id) return true;
    return false;
}

inline void update(int i, int x){
    for(int pos = i; pos < N; pos += lowbit(pos)){
        tree[pos] += x;
    }
}

ll query(int i){
    ll ans = 0;
    for(int pos = i; pos; pos -= lowbit(pos)){
        ans += tree[pos];
    }
    return ans;
}

int main(){
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++ ){
        scanf("%d", &B[i].value);
        B[i].id = i;
    }
    sort(B + 1, B + 1 + n, cmp);
    for(int i = 1; i <= n; i ++ )   A[B[i].id] = i;
    for(int i = 1; i <= n; i ++ ){
        sum += query(A[i]);
        update(A[i], 1);
    }
    sum = (ll) n * (n - 1) / 2 - sum;
    printf("%lld", sum);
    return 0;
}

习题3：数星星

题目：https://www.acwing.com/problem/content/description/1267/

#include<iostream>

using namespace std;

const int N = 32005;
#define lowbit(x) (x & (-x))

int tree[N];
int star[N];

inline void update(int i, int x){
    for(int pos = i; pos <= N; pos += lowbit(pos))  tree[pos] += x;
}

int query(int i){
    int res = 0;
    for(int pos = i; pos; pos -= lowbit(pos))   res += tree[pos];
    return res;
}

int main(){
    int n;
    cin>>n;
    for(int i = 1; i <= n; i ++ ){
        int x, y;
        cin>>x>>y;
        x ++;   //防止出现0
        update(x, 1);   
        star[query(x)] ++;
    }
    for(int i = 1; i <= n; i ++ )   cout<<star[i]<<"\n";
    return 0;
}

习题4：简单题

题目：https://www.acwing.com/problem/content/description/1270/

#include<iostream>

using namespace std;

const int N = 1E5 + 5;
#define lowbit(x) (x & (-x))

int tree[N];
int B[N];
int n, m;

inline void update(int i, int x = 1){
    for(int pos = i; pos <= N; pos += lowbit(pos))  tree[pos] += x;
}

int query(int i){
    int ans = 0;
    for(int pos = i; pos; pos -= lowbit(pos))   ans += tree[pos];
    return ans;
}

int main(){
    cin>>n>>m;
    for(int i = 1; i <= m; i ++ ){
        int op, l, r;
        cin>>op;
        if(op == 1){
            cin>>l>>r;
            update(l, 1);
            update(r + 1, -1);
        }
        else{
            cin>>l;
            int d = query(l);
            if(d % 2 == 0)  cout<<0<<'\n';
            else    cout<<1<<'\n';
        }
    }
    return 0;
}