单点修改,区间求和
题意
给定$n$个点,每次会询问一个区间的$[l, r]$的和,或者修改某个点的值。(最简单的模板题)
#include <iostream>
#define lc u << 1
#define rc u << 1 | 1
using namespace std;
const int N = 50010;
// 单点修改,区间查询
struct Node{
int l, r;
int s;
}tr[N * 4];
int w[N];
void pushup(int u)
{
tr[u].s = tr[lc].s + tr[rc].s;
}
void build (int u, int l, int r)
{
tr[u] = {l, r};
if (l == r) { tr[u].s = w[l]; return; }
int mid = l + r >> 1;
build (lc, l, mid), build (rc, mid + 1, r);
pushup(u);
}
void modify (int u, int x, int d)
{
if (tr[u].l == x && tr[u].r == x) tr[u].s += d;
else
{
int mid = tr[u].l + tr[u].r >> 1;
if (x <= mid) modify (lc, x, d);
else modify (rc, x, d);
pushup(u);
}
}
int query(int u, int l, int r)
{
if (tr[u].l >= l && tr[u].r <= r) return tr[u].s;
int mid = tr[u].l + tr[u].r >> 1;
int res = 0;
if (l <= mid) res += query(lc, l, r);
if (r > mid) res += query(rc, l, r);
return res;
}
void solve()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++) cin >> w[i];
build (1, 1, n);
string op;
int l, r, x, d;
while (cin >> op)
{
if (op == "End") break;
if (op == "Query") { cin >> l >> r; cout << query(1, l, r) << endl;}
else if (op == "Add") { cin >> x >> d; modify(1, x, d); }
else if (op == "Sub") { cin >> x >> d; modify(1, x, -d); }
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T = 1;
cin >> T;
for(int turn = 1 ; turn <= T ; turn++)
cout << "Case " << turn << ":\n", solve();
}