模板
单点修改的线段树
template<typename Avalue, typename Tvalue, // 序列类型，线段树类型
void (*set)(Tvalue&, Avalue), // 设置线段树初值
Tvalue (*op)(Tvalue, Tvalue), // 线段树合并
Tvalue (*c)(Tvalue, Tvalue)> // 线段树修改
struct lazysegment_tree {
std::vector<Tvalue> tree;
std::vector<Avalue> array;
size_t size;
#define LCH id * 2
#define RCH id * 2 + 1
lazysegment_tree() = default;
lazysegment_tree(size_t n, std::vector<Avalue>& a)
: tree((n + 1) << 2), array(a), size(n) {
build(1, 1, size);
}
void build(size_t n, std::vector<Avalue>& a) {
tree.resize((n + 1) << 2);
size = n;
array = a;
build(1, 1, size);
}
void build(int id, int l, int r) {
if (l == r) {
set(tree[id], array[l]);
return;
}
int mid = (l + r) >> 1;
build(LCH, l, mid);
build(RCH, mid + 1, r);
tree[id] = op(tree[LCH], tree[RCH]);
}
void clear() {
std::vector<Tvalue> tmp1;
std::vector<Avalue> 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 <= pos) {
tree[id] = c(tree[id], value);
return;
}
int mid = (l + r) >> 1;
if (pos <= mid) modify(LCH, l ,mid, pos, value);
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 <= pr) {
return tree[id];
}
int mid = (l + r) >> 1;
if (pr <= mid) return query(LCH, l, mid, pl, pr);
else if (pl > 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<bool (*cmp)(Tvalue, Tvalue)>
int lower_bound(int id, int l, int r, int pl, int pr, Tvalue d) {
if (pl <= l && r <= pr) {
int mid = (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<cmp>(LCH, l, mid, pl, pr, d);
else return lower_bound<cmp>(RCH, mid + 1, r, pl, pr, d);
}
int mid = (l + r) >> 1, lans = -1, rans = -1;
if (pl <= mid) lans = lower_bound<cmp>(LCH, l, mid, pl, pr, d);
if (pr > mid) rans = lower_bound<cmp>(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<bool (*cmp)(Tvalue, Tvalue)>
int lower_bound(int left, int right, Tvalue d) {
return lower_bound<cmp>(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<ll, tv, set, op, c> seg(n, a);
lazysegment_tree<ll, tv, set, op, c> 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<cmp>(left, right, d), 查找区间中第一个满足条件的下标，不存在得到 -1。
cmp 为函数指针 bool (*cmp)(Tvalue, Tvalue)，查找区间中第一个下标 pos 满足 cmp(a[pos], d) == true。
区间修改线段树
template<typename Avalue, typename Tvalue, typename Tag, // 序列类型，线段树类型， 标记类型
void (*set)(Tvalue&, Avalue), // 设置线段树初值
Tvalue (*op)(Tvalue, Tvalue), // 线段树合并
void (*tag)(Tvalue&, Tag&, Tag), // 下传标记
Tag (*e)()> // 清空标记(标记初值)
struct lazysegment_tree {
std::vector<Tvalue> tree;
std::vector<Tag> lazy;
std::vector<Avalue> array;
size_t size;
#define LCH id * 2
#define RCH id * 2 + 1
lazysegment_tree() = default;
lazysegment_tree(size_t n, std::vector<Avalue>& 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<Avalue>& a) {
tree.resize((n + 1) << 2);
lazy.resize((n + 1) << 2, e());
size = n;
array = a;
build(1, 1, size);
}
void build(int id, int l, int r) {
if (l == r) {
set(tree[id], array[l]);
return;
}
int mid = (l + r) >> 1;
build(LCH, l, mid);
build(RCH, mid + 1, r);
tree[id] = op(tree[LCH], tree[RCH]);
}
void clear() {
std::vector<Tvalue> tmp1;
std::vector<Tag> tmp2;
std::vector<Avalue> 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 <= pr) {
tag(tree[id], lazy[id], value);
return;
}
pushdown(id);
int mid = (l + r) >> 1;
if (pl <= mid) modify(LCH, l ,mid, pl, pr, value);
if (pr > 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 <= pr) {
return tree[id];
}
pushdown(id);
int mid = (l + r) >> 1;
if (pr <= mid) return query(LCH, l, mid, pl, pr);
else if (pl > 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<bool (*cmp)(Tvalue, Tvalue)>
int lower_bound(int id, int l, int r, int pl, int pr, Tvalue d) {
if (pl <= l && r <= pr) {
int mid = (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<cmp>(LCH, l, mid, pl, pr, d);
else return lower_bound<cmp>(RCH, mid + 1, r, pl, pr, d);
}
pushdown(id);
int mid = (l + r) >> 1, lans = -1, rans = -1;
if (pl <= mid) lans = lower_bound<cmp>(LCH, l, mid, pl, pr, d);
if (pr > mid) rans = lower_bound<cmp>(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<bool (*cmp)(Tvalue, Tvalue)>
int lower_bound(int left, int right, Tvalue d) {
return lower_bound<cmp>(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<ll, tv, ll, set, op, tag, e> seg(n, a);
lazysegment_tree<ll, tv, ll, set, op, tag, e> 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<cmp>(left, right, d), 查找区间中第一个满足条件的下标，不存在得到 -1。
cmp 为函数指针 bool (*cmp)(Tvalue, Tvalue)，查找区间中第一个下标 pos 满足 cmp(a[pos], d) == true。
