【板子】线段树

单点修改区间和

#include <vector> using namespace std; vector<int> 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; vector<int> 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); }

使用说明

1. 空间：tree、tag都要开4 * n；
2. 初始化：

   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);

3. 区间[L,R]加val：update(L, R, val, 1, 1, n)；
4. 查询区间[L,R]和：query(L, R, 1, 1, n)；//1，1，n用于函数递归，固定传整树
5. 核心关键点：pushdown必须在递归进入子节点前调用，保证子节点数据是最新的。