我们有一个数列$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;
}