SCP（大雾）复习板子？

唔

复习一下各种板子？

• 树状数组

其实忘得差不多了，只会lowbit了qaq

树状数组一的话就正常搞

#include<cstdio>
#define sev en
using namespace std;

#define N 500010

int n,m;
int tree[N];

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

void add(int x,int k) {
    while(x <= n) {
        tree[x] += k;
        x += lowbit(x);
    }
}

int query(int x) {
    int ans = 0;
    while(x) {
        ans += tree[x];
        x -= lowbit(x);
    }
    return ans;
}

int main() {
    scanf("%d%d",&n,&m);
    for(int i = 1; i <= n; i++) {
        int x;
        scanf("%d",&x);
        add(i,x);
    }
    for(int i = 1; i <= m; i++) {
        int op,x,k;
        scanf("%d%d%d",&op,&x,&k);
        if(op == 1)
            add(x,k);
        else
            printf("%d\n",query(k) - query(x - 1));
    }
    return 0;
}

BIT1

树状数组二用到了差分

反正是忘了嘤

#include<cstdio>
#define sev en
using namespace std;

#define N 500010

int n,m;
int tree[N];

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

void add(int x,int k) {
    while(x <= n) {
        tree[x] += k;
        x += lowbit(x);
    }
}

int query(int x) {
    int ans = 0;
    while(x) {
        ans += tree[x];
        x -= lowbit(x);
    }
    return ans;
}

int main() {
    scanf("%d%d",&n,&m);
    int st = 0;
    for(int i = 1; i <= n; i++) {
        int x;
        scanf("%d",&x);
        add(i,x - st);
        st = x;
    }
    for(int i = 1; i <= m; i++) {
        int op,x,y,k;
        scanf("%d",&op);
        if(op == 1) {
            scanf("%d%d%d",&x,&y,&k);
            add(x,k);
            add(y + 1,-k);
        } else {
            scanf("%d",&x);
            printf("%d\n",query(x));
        }
    }
    return 0;
}

BIT2