单点修改区间和#include vector using namespace std; vectorint tree, a; // 左右儿子快捷函数 int ls(int now) { return now 1; } int rs(int now) { return now 1 | 1; } // 向上更新子节点更新后更新父节点 void pushup(int now) { tree[now] tree[ls(now)] tree[rs(now)]; } // 建树now当前节点[l,r]对应原数组区间 void build(int now, int l, int r) { if (l r) { tree[now] a[l]; return; } int mid l r 1; build(ls(now), l, mid); build(rs(now), mid 1, r); pushup(now); } // 区间查询查询目标[l,r]当前节点p对应区间[pl,pr] int query(int l, int r, int p, int pl, int pr) { if (l pl pr r) return tree[p]; int pm pl pr 1, ans 0; if (l pm) ans query(l, r, ls(p), pl, pm); if (pm r) ans query(l, r, rs(p), pm 1, pr); return ans; } // 单点修改原数组id位置加v void update(int id, int v, int now, int l, int r) { if (l id r id) { tree[now] v; return; } int mid l r 1; if (id mid) update(id, v, ls(now), l, mid); else update(id, v, rs(now), mid 1, r); pushup(now); }区间修改区间和#include vector using namespace std; vectorint tree, a, tag; int ls(int now) { return now 1; } int rs(int now) { return now 1 | 1; } // 给节点p对应区间[pl,pr]统一加d更新值与懒标记 void addtag(int p, int pl, int pr, int d) { tag[p] d; tree[p] d * (pr - pl 1); } // 向上合并子节点信息 void pushup(int now) { tree[now] tree[ls(now)] tree[rs(now)]; } // 下放懒标记把当前节点标记传给左右儿子清空自身标记 void pushdown(int p, int pl, int pr) { if (!tag[p]) return; int mid pl pr 1; addtag(ls(p), pl, mid, tag[p]); addtag(rs(p), mid 1, pr, tag[p]); tag[p] 0; } // 建树 void build(int now, int l, int r) { if (l r) { tree[now] a[l]; return; } int mid l r 1; build(ls(now), l, mid); build(rs(now), mid 1, r); pushup(now); } // 区间查询 int query(int l, int r, int p, int pl, int pr) { if (l pl pr r) return tree[p]; pushdown(p, pl, pr); // 访问子节点前必须下放标记 int pm pl pr 1, ans 0; if (l pm) ans query(l, r, ls(p), pl, pm); if (pm r) ans query(l, r, rs(p), pm 1, pr); return ans; } // 区间修改[l,r]全部加d void update(int l, int r, int d, int p, int pl, int pr) { if (l pl pr r) { addtag(p, pl, pr, d); return; } pushdown(p, pl, pr); // 分裂区间前下放标记 int pm pl pr 1; if (l pm) update(l, r, d, ls(p), pl, pm); if (pm r) update(l, r, d, rs(p), pm 1, pr); pushup(p); }使用说明空间tree、tag都要开4 * n初始化int n; cin n; a.resize(n 1); tree.resize(4 * n); tag.resize(4 * n, 0); for (int i 1; i n; i) cin a[i]; build(1, 1, n);区间[L,R]加valupdate(L, R, val, 1, 1, n)查询区间[L,R]和query(L, R, 1, 1, n)//11n用于函数递归固定传整树核心关键点pushdown必须在递归进入子节点前调用保证子节点数据是最新的。