$第三板块 $ $ 数据结构 $

目录

1.树状数组1:单点修改，区间查询

# include <bits/stdc++.h>
# define sc scanf
# define pr printf
using namespace std;

const int N = 1e6 + 10;

typedef long long LL;

int n, q;
LL b[N];

inline int lowbit(int x){
    return x & (-x);
}

inline void add(int p, int x){
    while(p <= n){
        b[p] += x;
        p += lowbit(p);
    }
}

inline LL count(int p){
    LL res = 0;
    while(p){
        res += b[p];
        p -= lowbit(p);
    }

    return res;
}

int main(){
    sc("%d %d", &n, &q);

    for(int i = 1, x; i <= n; i ++) sc("%d", &x), add(i, x);

    while(q --){
        int x, y, z;
        sc("%d %d %d", &x, &y, &z);
        if(x == 1) add(y, z);

        else pr("%lld\n", count(z) - count(y - 1));
    }

    return 0;
}

2.树状数组2:区间修改，单点查询

# include <bits/stdc++.h>
# define sc scanf
# define pr printf
using namespace std;

const int N = 1e6 + 10;

typedef long long LL;

int n, q;
LL b[N];

inline int lowbit(int x){
    return x & (-x);
}

inline void add(int p, int x){
    while(p <= n){
        b[p] += x;
        p += lowbit(p);
    }
}

inline LL count(int p){
    LL res = 0;
    while(p){
        res += b[p];
        p -= lowbit(p);
    }

    return res;
}

int main(){
    sc("%d %d", &n, &q);

    for(int i = 1, x, y = 0; i <= n; i ++) sc("%d", &x), add(i, x - y), y = x;

    while(q --){
        int x;
        sc("%d", &x);
        if(x == 1){
            int l, r;
            sc("%d %d %d", &l, &r, &x);
            add(l, x);
            add(r + 1, -x);
        }

        else{
            sc("%d", &x);
            pr("%lld\n", count(x)); 
        }
    }

    return 0;
}

3.ST表——静态区间最大值

# include <bits/stdc++.h>
# define sc scanf
# define pr printf
using namespace std;

const int N = 1e5 + 10;

int n, m, x, y, l;
int lg[N], f[N][20];

int main(){
    sc("%d %d", &n, &m);

    lg[0] = -1;
    for(int i = 1; i <= n; i ++){
        sc("%d", &f[i][0]);
        lg[i] = lg[i >> 1] + 1; // 1 >> 1 == 0,而lg[0]==-1,所以lg[1]==0，少写了一个循环 
    }

    for(int j = 1; j <= lg[n]; j ++)
        for(int i = 1; i <= n - (1 << j) + 1; i ++)
            f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);

    while(m --){
        sc("%d %d", &x, &y);
        l = lg[y - x + 1];
        pr("%d\n", max(f[x][l], f[y - (1 << l) + 1][l]));
    }

    return 0;
}