差分

我们有一个数列$a$，如果我们新建一个数组$d$存储$a_i-a_{i-1}$，那么我们可以通过: $$\sum_1^x d_i$$求出$a_i$。因此，如果我们建立树状数组的时候利用差分的性质，区间更新$[L,R]$时只需要更新$L$和$R+1$即可，因为中间的差值是不变的。举个例子：

$a$: 1, 4, 5, 2, 3

$d$: 1, 3, 1, -3, 1

将$[2, 4]$的每个值+1:

$a$: 1, 5, 6, 3, 3

$d$: 1, 4, 1, -3, 0

可以看出，只有$L$和$R+1$受到影响，而其中的差值都是不变的。

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;

#define lowbit(x) (x & -x)

typedef long long ll;

int N, M;
int tree[5000050];
int x, y, k;

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

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

inline int read() {
    char ch = getchar();
    int a = 0;
    bool f = false;
    while(ch > '9' || ch < '0'){
        if(ch == '-') f = true;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9') {
        a = a * 10 + ch - '0';
        ch = getchar();
    }
    return f?-a:a;
}

int main() {
    N = read();M = read();
    int pre = 0;int p;
    for(int i=0;i<N;++i) {
        p = read();
        update(i + 1, p - pre);
        pre = p;
    }
    while(M--) {
        p = read();
        if(p == 1) {
            x = read();y = read();k = read();
            update(x, k);
            update(y+1, -k);
        } else { 
            x = read();
            printf("%lld\n", query(x));
        }
    }
    return 0;
}

树状数组区间修改+单点查询

差分

代码