模板单点修改的线段树
template // 线段树修改struct lazysegment_tree { std::vector tree; std::vector array; size_t size;#define LCH id * 2#define RCH id * 2 + 1 lazysegment_tree() = default; lazysegment_tree(size_t n, std::vector& a) : tree((n + 1) << 2), array(a), size(n) { build(1, 1, size); } void build(size_t n, std::vector& a) { tree.resize((n + 1) <> 1; build(LCH, l, mid); build(RCH, mid + 1, r); tree[id] = op(tree[LCH], tree[RCH]); } void clear() { std::vector tmp1; std::vector tmp3; tmp1.swap(tree); tmp3.swap(array); size = 0; } void modify(int id, int l, int r, int pos, Tvalue value) { if (pos <= l && r > 1; if (pos mid) modify(RCH, mid + 1, r, pos, value); tree[id] = op(tree[LCH], tree[RCH]); } Tvalue query(int id, int l, int r, int pl, int pr) { if (pl <= l && r > 1; if (pr mid) return query(RCH, mid + 1, r, pl, pr); return op(query(LCH, l, mid, pl, pr), query(RCH, mid + 1, r, pl, pr)); } template int lower_bound(int id, int l, int r, int pl, int pr, Tvalue d) { if (pl <= l && r > 1; if (!cmp(tree[id], d)) return -1; else if (l == r) return l; else if (cmp(tree[LCH], d)) return lower_bound(LCH, l, mid, pl, pr, d); else return lower_bound(RCH, mid + 1, r, pl, pr, d); } int mid = (l + r) >> 1, lans = -1, rans = -1; if (pl <= mid) lans = lower_bound(LCH, l, mid, pl, pr, d); if (pr > mid) rans = lower_bound(RCH, mid + 1, r, pl, pr, d); return (lans != -1 ? lans : rans); } void modify(int pos, Tvalue value) { modify(1, 1, size, pos, value); } Tvalue query(int pos) { return query(1, 1, size, pos, pos); } Tvalue query(int left, int right) { return query(1, 1, size, left, right); } template int lower_bound(int left, int right, Tvalue d) { return lower_bound(1, 1, size, left, right, d); }};初始化
// 区间最大值， 单点赋值using ll = long long;struct tv{ ll max;};void set(tv& a, ll b) { a = { b };}tv op(tv a, tv b) { return { std::max(a.max, b.max) };}tv c(tv a, tv b) { return b;}bool cmp(tv a, tv b) { return a.max >= b.max;}// 或者 lazysegment_tree seg(n, a);lazysegment_tree seg;seg.build(n, a);模板第一个参数 Avalue, 为序列 a 的值 类型。
第二个参数 Tvalue, 为 线段树值 的类型。
第三个参数void (*set)(Tvalue&, Avalue), 为线段树 赋初始值 的函数指针。
第四个参数Tvalue (*op)(Tvalue, Tvalue), 为线段树 合并两个段 的函数指针。
第五个参数Tvalue (*c)(Tvalue, Tvalue), 为线段树 单点修改 的函数指针。
可以全局创建，之后通过 build(n, a) 来构造线段树，也可以直接通过构造函数来创建局部变量，参数与 build 相同。
通过 clear 可以清空线段树。
修改
modify(pos, value), value 的类型与 线段树值 一致。
查询
返回值为 线段树的值 类型。
query(left, right), 区间查询。
query(pos), 单点查询。
线段树上二分
lower_bound(left, right, d), 查找区间中第一个满足条件的下标，不存在得到 -1。
cmp 为函数指针 bool (*cmp)(Tvalue, Tvalue)，查找区间中第一个下标 pos 满足 cmp(a[pos], d) == true。
区间修改线段树
template // 清空标记(标记初值)struct lazysegment_tree { std::vector tree; std::vector lazy; std::vector array; size_t size;#define LCH id * 2#define RCH id * 2 + 1 lazysegment_tree() = default; lazysegment_tree(size_t n, std::vector& a) : tree((n + 1) << 2), lazy((n + 1) << 2, e()), array(a), size(n) { build(1, 1, size); } void build(size_t n, std::vector& a) { tree.resize((n + 1) << 2); lazy.resize((n + 1) <> 1; build(LCH, l, mid); build(RCH, mid + 1, r); tree[id] = op(tree[LCH], tree[RCH]); } void clear() { std::vector tmp1; std::vector tmp2; std::vector tmp3; tmp1.swap(tree); tmp2.swap(lazy); tmp3.swap(array); size = 0; } void pushdown(int id) { if (lazy[id] == e()) return; tag(tree[LCH], lazy[LCH], lazy[id]); tag(tree[RCH], lazy[RCH], lazy[id]); lazy[id] = e(); } void modify(int id, int l, int r, int pl, int pr, Tag value) { if (pl <= l && r > 1; if (pl mid) modify(RCH, mid + 1, r, pl, pr, value); tree[id] = op(tree[LCH], tree[RCH]); } Tvalue query(int id, int l, int r, int pl, int pr) { if (pl <= l && r > 1; if (pr mid) return query(RCH, mid + 1, r, pl, pr); return op(query(LCH, l, mid, pl, pr), query(RCH, mid + 1, r, pl, pr)); } template int lower_bound(int id, int l, int r, int pl, int pr, Tvalue d) { if (pl <= l && r > 1; if (!cmp(tree[id], d)) return -1; else if (l == r) return l; pushdown(id); if (cmp(tree[LCH], d)) return lower_bound(LCH, l, mid, pl, pr, d); else return lower_bound(RCH, mid + 1, r, pl, pr, d); } pushdown(id); int mid = (l + r) >> 1, lans = -1, rans = -1; if (pl <= mid) lans = lower_bound(LCH, l, mid, pl, pr, d); if (pr > mid) rans = lower_bound(RCH, mid + 1, r, pl, pr, d); return (lans != -1 ? lans : rans); } void modify(int left, int right, Tag value) { modify(1, 1, size, left, right, value); } Tvalue query(int pos) { return query(1, 1, size, pos, pos); } Tvalue query(int left, int right) { return query(1, 1, size, left, right); } template int lower_bound(int left, int right, Tvalue d) { return lower_bound(1, 1, size, left, right, d); }};初始化
// 区间和， 区间加using ll = long long;struct tv{ ll sum; int size;};void set(tv& a, ll b) { a = { b, 1 };}tv op(tv a, tv b) { return { a.sum + b.sum, a.size + b.size };}void tag(tv& a, ll& b, ll c) { if (c == 0) return; a.sum += c * a.size; b += c;}ll e() { return 0;}// 或者 lazysegment_tree seg(n, a);lazysegment_tree seg;seg.build(n, a);模板第一个参数 Avalue, 为序列 a 的值 类型。
第二个参数 Tvalue, 为 线段树值 的类型。
第三个参数 Tag, 为 标记 的类型。
第四个参数void (*set)(Tvalue&, Avalue), 为线段树 赋初始值 的函数指针。
第五个参数Tvalue (*op)(Tvalue, Tvalue), 为线段树 合并两个段 的函数指针。
第六个参数void (*tag)(Tvalue&, Tag&, Tag), 为线段树 设置标记 的函数指针。
第七个参数Tag (*e)(), 为线段树 标记的初始值 的函数指针。
可以全局创建，之后通过 build(n, a) 来构造线段树，也可以直接通过构造函数来创建局部变量，参数与 build 相同。
通过 clear 可以清空线段树。
修改
modify(left, right, value), value 的类型与 标记 一致。
查询
返回值为 线段树的值 类型。
query(left, right), 区间查询。
query(pos), 单点查询。
线段树上二分
lower_bound(left, right, d), 查找区间中第一个满足条件的下标，不存在得到 -1。
cmp 为函数指针 bool (*cmp)(Tvalue, Tvalue)，查找区间中第一个下标 pos 满足 cmp(a[pos], d) == true。
其他
P3372 【模板】线段树 1
OI-wiki