让我们来一步一步理解！
1.向上更新
void push_up(int rt){//向上更新 sum[rt] = sum[rt << 1] + sum[rt << 1 | 1]; }
2.向下更新
void push_down(int rt, int m){ if(add[rt]){//若有标记,则将标记向下移动一层 add[rt << 1] += add[rt]; add[rt << 1 | 1] += add[rt]; sum[rt << 1] += (m - (m >> 1)) * add[rt]; sum[rt << 1 | 1] += (m >> 1) * add[rt]; add[rt] = 0;//取消本层标记 } }
3.开始建树
void build(int l, int r, int rt){//建树 add[rt] = 0; if(l == r){ scanf("%lld", &sum[rt]); return; } int mid = (l + r) >> 1; build(lson); build(rson); push_up(rt);//向上更新 }
4.区间更新
void update(int L, int R, ll key, int l, int r, int rt){//区间更新 if(L <= l && R >= r){ //该区间是完整的 sum[rt] += (r - l + 1) * key; add[rt] += key; return; } push_down(rt, r - l + 1);//向下更新,下传标记 int mid = (l + r) >> 1; if(L <= mid) update(L, R, key, lson); if(R > mid) update(L, R, key, rson); push_up(rt);//向上更新 }
5.区间求和
int query(int L, int R, int l, int r, int rt){//区间求和 if(L <= l && R >= r) return sum[rt]; push_down(rt, r - l + 1);//向下更新 int mid = (l + r) >> 1; int ans = 0; if(L <= mid) ans += query(L, R, lson); if(R > mid) ans += query(L, R, rson); return ans; }