$第三板块 $ $ 数据结构 $
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;
}