区间修改,区间求和
题意
给定$n$个点,每次操作要么将某个区间$[l, r]$都加上一个值,要么查询一个区间$[l,r]$的和。
(带懒标记的模板题)
#include <iostream>
#define lc u << 1
#define rc u << 1 | 1
using namespace std;
typedef long long LL;
const int N = 100010;
int w[N];
struct Node{
int l, r;
LL s, add;
}tr[N * 4];
void pushup (int u) { tr[u].s = tr[lc].s + tr[rc].s; }
void pushdown (int u)
{
if (tr[u].add)
{
LL &x = tr[u].add;
tr[lc].add += x; tr[lc].s += (tr[lc].r - tr[lc].l + 1) * x;
tr[rc].add += x; tr[rc].s += (tr[rc].r - tr[rc].l + 1) * x;
x = 0;
}
}
void build (int u, int l, int r)
{
tr[u].l = l, tr[u].r = 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 l, int r, int c)
{
if (tr[u].l >= l && tr[u].r <= r) tr[u].add += c, tr[u].s += (LL) (tr[u].r - tr[u].l + 1) * c;
else
{
pushdown (u);
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid) modify (lc, l, r, c);
if (r > mid) modify (rc, l, r, c);
pushup(u);
}
}
LL query (int u, int l, int r)
{
if (tr[u].l >= l && tr[u].r <= r) return tr[u].s;
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
LL res = 0;
if (l <= mid) res = query (lc, l, r);
if (r > mid) res += query (rc, l, r);
return res;
}
void solve()
{
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++ ) cin >> w[i];
build (1, 1, n);
while (m--)
{
char op[2];
int l, r, d;
cin >> op >> l >> r;
if (*op == 'Q') cout << query (1, l, r) << endl;
else cin >> d, modify (1, l, r, d);
}
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T = 1;
// cin >> T;
for(int turn = 1 ; turn <= T ; turn++)
solve();
}