这篇文章上次修改于 371 天前，可能其部分内容已经发生变化，如有疑问可询问作者。
ACM程序课算法笔记13——线线段树
线段树介绍
线段树的功能是维护一个数组，当然你可以用普通数组维护，线段树只是一种维护方式，它的特点是可以在O(LogN)的时间复杂度完成单点修改，区间修改，区间查询。
线段树结构
线段树的结构目的是为了维护区间的某个信息，比如总和，最大值，最小值等等。
按照树的思想，把区间进行多次的分割，同时，线段树使用数组存储树，使用数组表示树可以使根节点编号为1。
例如区间[1,5] 我们根据树先进行分割一次[1, 3]和[4, 5]这就是一个根节点变成两个子节点。同时在对它们俩进行一个拆分，此时[1,3]变成[1,2]和[3,3]。[4, 5]拆成[4,4]和[5,5]结构如下图
还有一点需要注意的是，线段树不一定要维护总和，我们可以用一个节点来做一些例子：(此处的加就负责节点的合并)
struct Node{
int valSum;
int valMax;
int valMin;
int lazy;
Node operator+(Node n2){
Node newNode;
newNode.valSum = valSum + n2.valSum;
newNode.valMax = max(valMax, n2.valMax);
newNode.valMin = min(valMin, n2.valMin);
return newNode;
}
Node operator+(int val){
Node newNode;
newNode.valSum += val;
newNode.valMax += val;
newNode.valMin += val;
return newNode;
}
}线段树的构建
对于建立一个这样的空间，我们可以发现很多都是在做重复的工作，所以不妨使用递归。再从下往上构建，颇有回溯味道。再根据数组储存树的基础知识，获取左子节点的方法是 index * 2 右子节点是 index * 2 +1
void build(vector<Node> &a, int left, int right, int arrNo) {
if (left == right) {
arr[arrNo] = a[left];
return;
}
int mid = (left + right) / 2; // 当然你可以选择防溢出
int leftTreeNo = arrNo * 2;
int rightTreeNo = arrNo * 2 + 1;
build(a, left, mid, leftTreeNo);
build(a, mid + 1, right, rightTreeNo);
// 特征值向上转移，这里使用相加，当然还可以使用其它方式
arr[arrNo] = arr[leftTreeNo] + arr[rightTreeNo];
}线段树的区间查询
线段树的区间查询不一定是，这里我们以求和为例子，也就是arr[1]储存1~5所有值的和，每个元素管理的区间的区间特征值作为它的值。同样，你也可以使用结构体来代表一个节点，这样就可以储存多个值。
线段树的区间查询有一个特点，一次查询最后是两个节点的和。例如当我求区间[2, 5] 实际上访问的就是节点[2, 2]和[3, 5]两个节点的和并。
为什么是两个：已知如果是多个一定连续，如果两个连续大概率合并成一个。
所以对于区间查询来说，主要问题就是如何找到这两个节点。
Node getsum(int queryLeft, int queryRight, int nodeLeft, int nodeRight, int node) {
if (queryLeft <= nodeLeft && nodeRight <= queryRight)
return arr[node];
int mid = (nodeLeft + nodeRight) / 2; // 当然你可以选择防溢出
int leftTreeNo = node * 2;
int rightTreeNo = node * 2 + 1;
Node sum = {0, MAX, MIN, 0};
if (queryLeft <= mid)
sum = sum + getsum(queryLeft, queryRight, nodeLeft, mid, leftTreeNo);
if (mid < queryRight)
sum = sum + getsum(queryLeft, queryRight, mid + 1, nodeRight, rightTreeNo);
return sum;
}通过递归从上往下去寻找即可。见上代码。
线段树的区间修改
根据简单的判断我们可以得出，线段树如果要修改一个值，就要同步修改上面的所有值，但如果修改一个区间，同样我们要进行很大的成本修改，对此，咱们提出了懒惰标级。
懒惰标记
懒惰标记的目的就是延迟对具体底下的值进行修改。例如我要修改的是区间[1, 3]的所有值，那我先只改[1, 2]和[3, 3]，如果我之后查询的是[1, 4] 和 [1, 5]那么实际上就没有必要落实到1和2个题元素上，那我们就把这个修改暂时留在[1, 2]的这个节点上，等到我真的要去查询[1, 1]或者[2, 2]，我再把这个修改下沉。
以下是关于懒惰标记的区间更新(区间增加或者区间减少)
void update(int queryLeft, int queryRight, int nodeLeft, int nodeRight, int node, int add) {
if (queryLeft <= nodeLeft && nodeRight <= queryRight) {
arr[node] = arr[node] + (nodeRight - nodeLeft + 1) * add;
arr[node].lazy += add;
return;
}
int mid = (nodeLeft + nodeRight) / 2;
int leftTreeNo = node * 2;
int rightTreeNo = node * 2 + 1;
if (arr[node].lazy and nodeLeft != nodeRight) { // 向下转移懒惰标记
arr[leftTreeNo] = arr[leftTreeNo] + arr[node].lazy * (mid - nodeLeft + 1);
arr[rightTreeNo] = arr[rightTreeNo] + arr[node].lazy * (nodeRight - mid);
arr[leftTreeNo].lazy += arr[node].lazy;
arr[rightTreeNo].lazy += arr[node].lazy;
arr[node].lazy = 0;
}
if (queryLeft <= mid)
update(queryLeft, queryRight, nodeLeft, mid, leftTreeNo, add);
if (mid < queryRight)
update(queryLeft, queryRight, mid + 1, nodeRight, rightTreeNo, add);
arr[node] = arr[leftTreeNo] + arr[rightTreeNo];
}
以下是关于懒惰标记的区间查询
我们说过，一旦查询到下面，就需要对懒惰标记进行下移
Node getsum(int queryLeft, int queryRight, int nodeLeft, int nodeRight, int node) {
if (queryLeft <= nodeLeft && nodeRight <= queryRight)
return arr[node];
int mid = (nodeLeft + nodeRight) / 2;
int leftTreeNo = node * 2;
int rightTreeNo = node * 2 + 1;
if (arr[node].lazy and nodeLeft != nodeRight) { // 向下转移懒惰标记
arr[leftTreeNo] = arr[leftTreeNo] + arr[node].lazy * (mid - nodeLeft + 1);
arr[rightTreeNo] = arr[leftTreeNo] + arr[node].lazy * (nodeRight - mid);
arr[leftTreeNo].lazy += arr[node].lazy;
arr[rightTreeNo].lazy += arr[node].lazy;
arr[node].lazy = 0;
}
Node sum = {0, MAX, MIN, 0};
if (queryLeft <= mid)
sum = sum + getsum(queryLeft, queryRight, nodeLeft, mid, leftTreeNo);
if (mid < queryRight)
sum = sum + getsum(queryLeft, queryRight, mid + 1, nodeRight, rightTreeNo);
return sum;
}当然也可以把对区间的操作从“都增加一个值add”变成“都变成一个值x”。
此时的lazy标签就代表要改的值了，但需要注意一点，主要另一个值来判断是否要修改，因为lazy标签为0时，代表的是全部值改为0而并不是不修改元素。
一些优化
- 在叶子节点处无需下放懒惰标记，所以懒惰标记可以不下传到叶子节点。
- 动态创建子节点，在不访问的时候就不创建节点。
- 标记永久化：如果确定懒惰标记不会在中途被加到溢出，那么就可以将标记永久化。标记永久化可以避免下传懒惰标记，只需在进行询问时把标记的影响加到答案当中，从而降低程序常数。也就是不需要修改子节点的值，只需要一直利用路途中的懒惰标记即可。
25.3.4更新
jiangly线段树板子
#define ls p << 1
#define rs p << 1 | 1
#define Mid (pl + pr >> 1)
template<class Info, class Tag>
struct LazySegmentTree {
int n;
vector<Info> info;
vector<Tag> tag;
LazySegmentTree(int siz) : n(siz) {
info.resize(n << 2);
tag.resize(n << 2);
}
LazySegmentTree(vector<Info>& init, int siz) : n(siz) {
info.resize(n << 2);
tag.resize(n << 2);
auto build = [&](auto&& self, int p, int pl, int pr) -> void {
if (pl == pr) {
info[p] = init[pl];
return;
}
self(self, ls, pl, Mid);
self(self, rs, Mid + 1, pr);
push_up(p);
};
build(build, 1, 1, n);
}
void push_up(int p) {
info[p] = info[ls] + info[rs];
}
void apply(int p, const Tag& t) {
info[p].apply(t);
tag[p].apply(t);
}
void push_down(int p) {
apply(ls, tag[p]);
apply(rs, tag[p]);
tag[p] = Tag();
}
void update(int x, int p, int pl, int pr, const Info& a) {
if (pl == pr) {
info[p] = a;
return;
}
push_down(p);
if (x <= Mid) update(x, ls, pl, Mid, a);
else update(x, rs, Mid + 1, pr, a);
push_up(p);
}
void update(int x, const Info& a) {
update(x, 1, 1, n, a);
}
void update(int L, int R, int p, int pl, int pr, const Tag& t) {
if (L <= pl && pr <= R) {
apply(p, t);
return;
}
push_down(p);
if (L <= Mid) update(L, R, ls, pl, Mid, t);
if (R > Mid) update(L, R, rs, Mid + 1, pr, t);
push_up(p);
}
void update(int L, int R, const Tag& t) {
update(L, R, 1, 1, n, t);
}
Info query(int L, int R, int p, int pl, int pr) {
if (L > pr || R < pl) return Info();
if (L <= pl && pr <= R) return info[p];
push_down(p);
return query(L, R, ls, pl, Mid) + query(L, R, rs, Mid + 1, pr);
}
Info query(int L, int R) {
return query(L, R, 1, 1, n);
}
bool check(const Info& a) {
return 1;
}
Info temp;
int findFirst(int p, int pl, int pr, int L) {
if (pr < L) return -1;
if (pl >= L && !check(temp + info[p])) {
temp = temp + info[p];
return -1;
}
if (pl == pr) return pl;
push_down(p);
int res = findFirst(ls, pl, Mid, L);
if (res == -1) {
res = findFirst(rs, Mid + 1, pr, L);
}
return res;
}
int findFirst(int L) {
temp = Info();
return findFirst(1, 1, n, L);
}
};有更好的应用性，根据自己的使用选择。
// 懒标记，默认所有的元素都有一个初始的懒标记
struct Tag {
int x {-1}; // 需要一个标记来代表当前标记是否为空，即所有元素都有一个空标记。
void apply(const Tag &t) {
// 懒标记结合
}
};
struct Info {
// 自行定义结构内函数 例如区间如下定义
int l, r;
Info() {}
Info(int pos, int val) {
l = r = pos;// 这是一个维护区间的定义
}
void apply(const Tag &t) {
if (t.x == -1) {
return; // 无论Tag是否为空，在pushdown都会对元素进行apply一个初始标记
}
// 懒标记非空，将懒标记生效，运行完后，该节点上的懒标记会被重新初始化。
}
};
Info operator+ (const Info &a, const Info &b) {
// 处理两个节点相加的情况，需要自行判断结合。
return newNode;
}以下作为使用例，多调试多使用。
struct Tag {
int x {-1};
void apply(const Tag &t) {
if (t.x > 0) {
x = t.x;
}
}
};
struct Info {
int st[4] = {0};
int l = 0, r = 0;
ll f[4] = {0};
Info() {}
Info(int p, int x) {
l = r = p;
for (int i = 1; i <= 3; i++) {
st[i] = i == x ? x : 6 - x - i;
f[i] = i == x ? 0 : 1;
}
}
void apply(const Tag &t) {
if (t.x == -1) {
return;
}
for (int i = 1; i <= 3; i++) {
st[i] = i == t.x ? t.x : 6 - t.x - i;
f[i] = i == t.x ? 0 : 1;
}
}
};
Info operator+ (const Info &a, const Info &b) {
if (a.l == 0) {
return b;
}
if (b.l == 0) {
return a;
}
Info c;
c.l = a.l;
c.r = b.r;
ll v = t[a.r - a.l + 1];
for (int i = 1; i <= 3; i++) {
c.st[i] = a.st[b.st[i]];
c.f[i] = (v * b.f[i] % mod + a.f[b.st[i]]) % mod;
}
return c;
}