P3368 【模板】树状数组 2 区间修改 + 单点查询
作者:
多米尼克領主的致意
,
2024-05-13 14:25:31
,
所有人可见
,
阅读 5
#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) x&(-x)
// typedef long long ll;
const int N = 5e5 + 10;
int n, m;
int a[N], b[N], tree[N];
void add(int x, int d){
while(x < N){
tree[x] += d;
x += lowbit(x);
}
}
int sum(int x){
int ans = 0;
while(x > 0){
ans += tree[x];
x -= lowbit(x);
}
return ans;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for(int i = 1;i <= n;i++){
cin >> a[i];
b[i] = a[i] - a[i - 1];//差分数组
add(i, b[i]);
}
while(m--){
int op, x, k;
cin >> op;
if(op == 1){
int l, r;
cin >> l >> r >> k;
add(l, k);
add(r + 1, -k);
}
if(op == 2){
cin >> x;
cout << sum(x) << endl;
}
}
return 0;
}