https://www.cnblogs.com/xenny/p/9801703.html
#include<iostream>
using namespace std;
const int maxn = 1e4 + 10;
int a[maxn], t[maxn << 2], lazy[maxn << 2];
void build(int root, int l, int r)
{
if (l == r)
{
t[root] = a[l];
return;
}
int m = (l + r) / 2;
build(root * 2, l, m);
build(root * 2 + 1, m + 1, r);
t[root] = t[root * 2] + t[root * 2 + 1];
}
void update(int p, int val, int l, int r, int root)
{
if (l == r)
{
t[l] += val;
return;
}
int m = (l + r) / 2;
if (p < m)update(p, val, l, m, root);
else if (p > m)update(p, val, m + 1, r, root);
t[root] = t[root * 2] + t[root * 2 + 1];
}
int query(int L, int R, int l, int r, int root)
{
if (L <= l && r <= R)
{
return t[root];
}
int res = 0;
int mid = (l + r) / 2;
if (L < mid)res += query(L, R, l, mid, root * 2);
if (R > mid)res += query(L, R, mid + 1, r, root * 2 + 1);
return res;
}
void pushdown(int root)
{
if (lazy[root])
{
lazy[root * 2] += lazy[root];
lazy[root * 2 + 1] += lazy[root];
t[root * 2] += lazy[root * 2];
t[root * 2 + 1] += lazy[root * 2 + 1];
lazy[root] = 0;
}
}
void updatelazy(int L,int R,int val,int l,int r,int root){
if (L <= l && r <= R) {
lazy[root] += val;
return;
}
pushdown(root);
int mid = (l + r) / 2;
if (L <= mid)update(L, R, val, l, mid, root * 2);
if (R > mid)update(L, R, val, mid + 1, R, root * 2 + 1);
t[root] = t[root * 2] + t[root * 2 + 1];
}
int querylazy(int L, int R, int l, int r, int root)
{
if (L <= l && r <= R)
{
return t[root];
}
pushdown(root);
int res = 0;
int mid = (l + r) / 2;
if (L <= mid)res += querylazy(L, R, l, mid, root * 2);
if (R > mid)res += querylazy(L, R, mid + 1, r, root * 2 + 1);
return res;
}
