单点修改,区间查询
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
int n, m, tree[N];
int lowbit(int k){
return k & -k;
}
void update(int x, int k){
while (x <= n){
tree[x] += k;
x += lowbit(x);
}
}
int query(int x){
int ans = 0;
while (x != 0){
ans += tree[x];
x -= lowbit(x);
}
return ans;
}
void solve(){
cin >> n >> m;
for (int i = 1; i <= n; i++){
int a;
scanf("%d", &a);
update(i, a);
}
for (int i = 1; i <= m; i++){
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
if (a == 1) update(b, c);
else cout << query(c) - query(b - 1) << "\n";
}
}
int main(){
solve();
return 0;
}
应用:https://www.luogu.com.cn/problem/P3374
区间修改,单点查询(差分)
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
int n, m, tree[N], num[N];
int lowbit(int k){
return k & -k;
}
void update(int x, int k){
while (x <= n){
tree[x] += k;
x += lowbit(x);
}
}
int query(int x){
int ans = 0;
while (x != 0){
ans += tree[x];
x -= lowbit(x);
}
return ans;
}
void solve(){
cin >> n >> m;
for (int i = 1; i <= n; i++)
scanf("%d", &num[i]);
for (int i = 1; i <= m; i++){
int op, l, r, x;
scanf("%d", &op);
if (op == 1){
scanf("%d%d%d", &l, &r, &x);
update(l, x);
update(r + 1, -x);
}
else {
scanf("%d", &x);
cout << num[x] + query(x) << "\n";
}
}
}
int main(){
solve();
return 0;
}
应用:https://www.luogu.com.cn/problem/P3368