天涯头条

【学习笔记】线段树

2024-07-27 18:43 由 5t0_0r2 发表于 #其他

本文 Markdown 源代码冲刺 \(3000\) 行中，目前行数：\(2794\) 行。

【0】线段树简介

【0.1】线段树是干什么的

线段树是一种基于分治的树形数据结构，可以处理很多区间问题，值域问题。

【0.2】线段树的形态

线段树作为一棵二叉树，其左子节点维护的是左半区间的信息，右子节点维护的是右半区间的信息。

其中对于一个区间 \([l,r]\)，左半区间是 \([l,\lfloor \frac{l + r}{2} \rfloor]\)，右半区间是 \((\lfloor \frac{l + r}{2} \rfloor,r]\)。可以看出，这里的左右区间是严格对半分的。

举一个 OI-wiki 的例子，当前序列 \(a = \{10,11,12,13,14\}\)，我们要维护 \(a\) 的区间和，则建立的线段树形态如下：

其中黑色字代表的是当前区间的和，红色字代表当前区间。

结合图例，我们不难得出：

  1. 线段树每个节点要么没有子节点（为叶节点），要么有两个子节点。这个好理解，因为一个区间要么不可分割（长度为 \(1\)），要么可以分割为左右两个区间（对应左右两个子节点）。

  2. 线段树的树高为 \(O(\log n)\)。

【0.3】线段树的存储

线段树一般有两种存储方式：堆式存储和链式存储。

堆式存储是最常用的存储方法，从上图看出，线段树是相对比较满的二叉树，因此可以使用和堆一样的儿子表示法。

链式存储虽然可以节约空间，但在一般的时候并不实用。不过，在有些题目中序列长度 \(n\) 巨大但是用到的节点远没到 \(O(n)\) 级别，这个时候可以使用【3.1】中的动态开点线段树，其利用的就是线段树的链式存储。

【1】线段树的基本操作

【1.0】建立线段树

线段树基于分治，建树本质也是一个分治的过程：

  1. 对于非叶节点，我们递归进入左右子节点建树，并合并左右子节点信息。

  2. 对于叶节点，此时对应的区间长度为 \(1\)，直接令叶节点维护的值为原序列上对应位置的值，这是递归边界。

void build(int root,int l,int r){
	if(l == r){//到达叶节点
		t[root].val = a[l];//val维护的可以是区间和、区间最值等（但区间长度都为1了肯定是这个位置上的值啊）
		return;
	}
	build(lchild,l,mid);
	build(rchild,mid + 1,r);
	push_up(root);
}

其中 push_up 是自定义的，用于合并两个子节点的区间信息，在维护区间加 + 区间求和的问题中 push_up 就是将两个子节点的值加起来：

void push_up(int root){
	t[root].val = t[lchild].val + t[rchild].val;
}

上述代码复杂度为 \(O(n)\)。

当然，建树也可以用 \(n\) 次单点修改来完成，不过这样复杂度会退化至 \(O(n \log n)\)，在 \(n\) 较大的时候不适用。

【1.1】单点修改/单点查询

单点修改和单点查询是简单的，由线段树的定义，我们从根节点开始，找到需要查询的位置是在哪个半区间，并进入对应的节点。当进入根节点时，直接执行修改/查询操作即可。

注意修改操作返回时也要执行 push_up。

//将 pos 上的数加 v 
void update(int root,int l,int r,int pos,int v){
	if(l == r)//到达叶子节点，直接修改
		t[root].val = v;
	if(l <= mid)
		update(lchild,l,mid,pos,v);
	else
		update(rchild,mid + 1,r,pos,v);
	push_up(root);//最后还要更新节点信息 
}

//查询 pos 上的数 
int query(int root,int l,int r,int pos){
	if(l == r)//到达叶子节点，直接返回 
		return t[root].val;
	if(l <= mid)
		return query(lchild,l,mid,pos);
	else
		return query(rchild,mid + 1,r,pos);
}

上述代码复杂度显然与树高有关，【0.2】中提到线段树的树高为 \(O(\log n)\)，所以单点修改和单点查询为 \(O(\log n)\)。

【1.2】区间修改/区间查询

只支持单点修改/单点查询的线段树是没有意义的，因为直接用数组就能维护。

对于区间修改，暴力修改所有叶子节点是很慢的，我们不妨思考一个问题：如果所有修改都是全局加，要用线段树维护，怎么办？

这是一个很简单的问题：我们在根节点维护一个标记，每次全局加 \(k\) 就将这个标记加 \(k\)，查询一个区间和就是原数组的区间和加区间长度乘标记。

但是，修改不可能永远是全局修改。

我们再思考一个问题：如果所有修改都是修改左半区间（\([1,\lfloor \frac{l + r}{2} \rfloor]\)），要用线段树维护，怎么办？,

这个问题和上一个问题很类似，我们就只用在根节点的左子节点上维护一个标记即可。

这两个例子启发我们：对于一个对应到一个线段树上节点的区间，都可以用一个标记来维护区间加操作，我们称这种标记为“懒标记”（又称延时标记）

那么对于一般的区间怎么用懒标记呢？

这不是一样的吗？无非就是多打几个标记的问题吗。

一个区间可以拆分为多个节点表示的区间，我们就只用将这些节点都打标记就可以了。

打标记说着很简单，但还是有一些细节的。

下文以区间加 + 区间和查询为例讲解。

【1.2.1】打标记

如果我们要在一个节点打标记，我们不仅要将该节点的标记加上 \(v\)，还要更新该节点维护的区间和（否则接下来查询该节点的区间和时还要重新更新，非常混乱）。

以下是将节点 root 的标记加上 \(v\) 的代码：

void make_tag(int root,int len,int v){//len为该节点维护区间的长度
	t[root].tag += v;
	t[root].sum += v * len;
}

【1.2.2】下传标记

下传标记就是将一个节点的两个子节点分别打上该节点的标记，并清空该节点的标记。

注意，有些区间修改（例如区间推平，就是将整个区间修改为同一个数），是用特殊值（例如 \(\inf\)）来代表没有操作，这个时候就要特判标记是否为特殊值了。

以下是区间加下传标记代码：

void push_down(int root,int l,int r){
	make_tag(lchild,len(l,mid),t[root].tag);
	make_tag(rchild,len(mid + 1,r),t[root].tag);
	t[root].tag = 0;
}

【1.2.3】区间修改/查询的代码

区间修改的代码就是从根节点开始不断往下走，如果一个节点完全包含在操作区间中，那么直接打标记，否则递归进入左右区间，这样打标记的节点刚好能覆盖操作区间。

void update(int root,int l,int r,int L,int R,int v){//root是当前节点，l、r是当前节点表示的区间，L、R是操作区间，v是区间加的值（下同）。
	if(out_range(l,r,L,R))//无交直接返回
		return;
	if(in_range(l,r,L,R)){
		make_tag(root,len(l,r),v);
		return;
	}
	push_down(root,l,r);
	update(lchild,l,mid,L,R,v);
	update(rchild,mid + 1,r,L,R,v);
	push_up(root);
}

查询是类似的，也是当遍历到完全包含在查询区间的区间时直接返回当前节点的值，并且也要一路下传标记。

//查询区间 [L,R] 中所有数的和 
int query(int root,int l,int r,int L,int R){
	if(out_range(l,r,L,R))
		return 0;
	if(in_range(l,r,L,R))
		return t[root].sum;
	push_down(root,l,r);
	return query(lchild,l,mid,L,R) + query(rchild,mid + 1,r,L,R);
}

被覆盖到的节点数是 \(O(\log n)\) 级别的，所以区间操作的复杂度也是 \(O(\log n)\)。

例题 1：线段树1

本题就是一个区间加 + 区间求和的模板，直接按照上述讲的内容拼接即可，详见代码。

#include<bits/stdc++.h>
#define int long long
#define mid ((l + r) >> 1)
#define lchild (root << 1)
#define rchild ((root << 1) + 1)
using namespace std;
const int N = 1e5 + 9;
int n,m;
int a[N];
struct node{
	int sum;
	int tag;//区间加标记 
} t[N << 2];

int len(int l,int r){
	return r - l + 1;
}

bool in_range(int l,int r,int L,int R){//[l,r]是否在修改/查询区间[L,R]中 
	return L <= l && r <= R;
}
bool out_range(int l,int r,int L,int R){//[l,r]是否与修改/查询区间[L,R]无交集 
	return l > R || r < L;
}

void push_up(int root){
	t[root].sum = t[lchild].sum + t[rchild].sum;
}

void make_tag(int root,int len,int v){
	t[root].tag += v;
	t[root].sum += v * len;
}
void push_down(int root,int l,int r){
	make_tag(lchild,len(l,mid),t[root].tag);
	make_tag(rchild,len(mid + 1,r),t[root].tag);
	t[root].tag = 0;
}

void build(int root,int l,int r){
	if(l == r){//到达叶节点
		t[root].sum = a[l];
		return;
	}
	build(lchild,l,mid);
	build(rchild,mid + 1,r);
	push_up(root);
}

//将区间 [L,R] 内的所有数加 v 
void update(int root,int l,int r,int L,int R,int v){//root是当前节点，l、r是当前节点表示的区间，L、R是操作区间，v是区间加的值（下同）。
	if(out_range(l,r,L,R))
		return;
	if(in_range(l,r,L,R)){
		make_tag(root,len(l,r),v);
		return;
	}
	push_down(root,l,r);
	update(lchild,l,mid,L,R,v);
	update(rchild,mid + 1,r,L,R,v);
	push_up(root);
}

//查询区间 [L,R] 中所有数的和 
int query(int root,int l,int r,int L,int R){
	if(out_range(l,r,L,R))
		return 0;
	if(in_range(l,r,L,R))
		return t[root].sum;
	push_down(root,l,r);
	return query(lchild,l,mid,L,R) + query(rchild,mid + 1,r,L,R);
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> n >> m;
	for(int i = 1;i <= n;i++)
		cin >> a[i];
	build(1,1,n);
	while(m--){
		int op,l,r,v;
		cin >> op >> l >> r;
		if(op == 1){
			cin >> v;
			update(1,1,n,l,r,v); 
		}
		else
			 cout << query(1,1,n,l,r) << '\n';
	}
	return 0;
}

例题 2：开关

区间和（等于区间 \(1\) 的个数） + 区间 0/1 翻转。

区间和是一样的，只用考虑区间 0/1 翻转如何打标记。

其实也不难，当一个区间内的所有 \(0\) 变成 \(1\)，所有 \(1\) 变成 \(0\) 时，假设该区间的长度为 \(len\)，原来 \(1\) 的个数（区间和）为 \(sum\)，那么现在 \(1\) 的个数（区间和）变为 \(len - sum\)。

然后再维护一个翻转的标记，\(0\) 代表区间没有翻转，\(1\) 代表该区间要翻转，每次将这个标记异或 \(1\) 即可。

注意当标记为 \(0\) 的时候不用下传标记。

#include<bits/stdc++.h>
#define mid ((l + r) >> 1)
#define lchild (root << 1)
#define rchild ((root << 1) + 1)
using namespace std;
const int N = 1e5 + 9;
int n,m;
struct node{
	int sum;//区间中1的个数（打开灯的个数） 
	int tag;//翻转标记（本质是翻转次数的奇偶性） 
} t[N << 2];

int len(int l,int r){
	return r - l + 1;
}

bool in_range(int l,int r,int L,int R){
	return L <= l && r <= R;
}
bool out_range(int l,int r,int L,int R){
	return l > R || r < L;
}

void push_up(int root){
	t[root].sum = t[lchild].sum + t[rchild].sum;
}
void make_tag(int root,int len){
	t[root].tag ^= 1;
	t[root].sum = len - t[root].sum;
}
void push_down(int root,int l,int r){
	if(t[root].tag){
		make_tag(lchild,len(l,mid));
		make_tag(rchild,len(mid + 1,r));
		t[root].tag = 0;
	}
}

void update(int root,int l,int r,int L,int R){
	if(out_range(l,r,L,R))
		return;
	if(in_range(l,r,L,R)){
		make_tag(root,len(l,r));
		return;
	}
	push_down(root,l,r);
	update(lchild,l,mid,L,R);
	update(rchild,mid + 1,r,L,R);
	push_up(root);
}
int query(int root,int l,int r,int L,int R){
	if(out_range(l,r,L,R))
		return 0;
	if(in_range(l,r,L,R))	
		return t[root].sum;
	push_down(root,l,r);
	return query(lchild,l,mid,L,R) + query(rchild,mid + 1,r,L,R);
}


int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> n >> m;
	while(m--){
		int op,l,r;
		cin >> op >> l >> r;
		if(op == 0)
			update(1,1,n,l,r);
		else
			cout << query(1,1,n,l,r) << '\n';
	}
	return 0;
}

例题 3：XOR on Segment

上一题的进阶版。

本题用到的技巧：拆位。

单独对每一位开一个线段树，修改时如果 \(x\) 的第 \(i\) 位为 \(1\) 就相当于上一题的区间 0/1 翻转，直接在第 \(i\) 棵线段树上执行操作即可。

#include<bits/stdc++.h>
#define int long long
#define mid ((l + r) >> 1)
#define lchild (root << 1)
#define rchild ((root << 1) + 1)
using namespace std;
const int N = 1e5 + 9,LOGV = 20;
int n,m;
int a[N];
struct node{
	int sum,tag;
} t[N << 2][LOGV];


int len(int l,int r){
	return r - l + 1;
}

bool in_range(int l,int r,int L,int R){//[l,r]是否在修改/查询区间[L,R]中 
	return L <= l && r <= R;
}
bool out_range(int l,int r,int L,int R){//[l,r]是否与修改/查询区间[L,R]无交集 
	return l > R || r < L;
}

void push_up(int root){
	for(int i = 0;i < LOGV;i++)
		t[root][i].sum = t[lchild][i].sum + t[rchild][i].sum;
}

void make_tag(int root,int len,int i){
	t[root][i].tag ^= 1;
	t[root][i].sum = (len << i) - t[root][i].sum;
}
void push_down(int root,int l,int r){
	for(int i = 0;i < LOGV;i++){
		if(t[root][i].tag){
			make_tag(lchild,len(l,mid),i);
			make_tag(rchild,len(mid + 1,r),i);
			t[root][i].tag = 0;
		}
	}
}

void build(int root,int l,int r){
	if(l == r){
		for(int i = 0;i < LOGV;i++)
			t[root][i].sum = (a[l] & (1 << i));
		return;
	}
	build(lchild,l,mid);
	build(rchild,mid + 1,r);
	push_up(root);
}
void update(int root,int l,int r,int L,int R,int v){
	if(out_range(l,r,L,R))
		return;
	if(in_range(l,r,L,R)){
		for(int i = 0;i < LOGV;i++)
			if(v & (1 << i))
				make_tag(root,len(l,r),i);
		return;
	}
	push_down(root,l,r);
	update(lchild,l,mid,L,R,v);
	update(rchild,mid + 1,r,L,R,v);
	push_up(root);
}
int query(int root,int l,int r,int L,int R){
	if(out_range(l,r,L,R))
		return 0;
	if(in_range(l,r,L,R)){
		int ret = 0;
		for(int i = 0;i < LOGV;i++)//累加所有线段树这个节点的结果
			ret += t[root][i].sum;
		return ret;
	}
	push_down(root,l,r);
	return query(lchild,l,mid,L,R) + query(rchild,mid + 1,r,L,R);
}


signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> n;
	for(int i = 1;i <= n;i++) 
		cin >> a[i];
	build(1,1,n);
	cin >> m;
	while(m--){
		int op,l,r;
		cin >> op >> l >> r;
		if(op == 1)
			cout << query(1,1,n,l,r) << '\n';
		else if(op == 2){
			int x;
			cin >> x;
			update(1,1,n,l,r,x);
		}
		
	}
	return 0;
}

例题 4：方差

稍微需要一点数学推导的线段树题。

区间加不用说，和上一题一模一样。

区间平均数也简单，就是区间和除以区间长度。

区间方差需要进行转化。观察提示中关于方差的式子，将其展开得：

\[\frac{1}{n} \sum^{n}_{i = 1}(A_i - \overline A) ^ 2 = \frac{1}{n} \sum^{n}_{i = 1}(A_i ^ 2 - 2 A_i \overline A + \overline A^2) \]

\[= \frac{1}{n} \sum^{n}_{i = 1}A_i ^ 2 - 2\overline A \frac{\sum^{n}_{i = 1}A_i}{n}+ \overline A^2 \]

\[= \frac{1}{n} \sum^{n}_{i = 1}A_i ^ 2 - 2\overline A ^ 2 + \overline A^2 \]

\[= \frac{1}{n} \sum^{n}_{i = 1}A_i ^ 2 - \overline A ^ 2 \]

这样，我们就只用求区间平均值和区间平方和。

求区间平均值的方法是一样的，区间平方和也需要一定的推导。

区间平方和的查询、合并和区间和一样是直接加，重点在于如何更新。

假设我们已知 \(a_l ^ 2 + a_{l + 1} ^ 2 + \cdots + a_{r - 1} ^ 2 + a_r ^ 2\)，要求 \((a_l + k) ^ 2 + (a_{l + 1} + k) ^ 2 + \cdots + (a_{r - 1} + k) ^ 2 + (a_r + k) ^ 2\)。

还是展开：

\[(a_l + k) ^ 2 + (a_{l + 1} + k) ^ 2 + \cdots + (a_{r - 1} + k) ^ 2 + (a_r + k) ^ 2 \]

\[=(a_l ^ 2 + 2 a_l k + k ^ 2) + (a_l ^ 2 + 2 a_l k + k ^ 2) + \cdots + (a_l ^ 2 + 2 a_l k + k ^ 2) + (a_l ^ 2 + 2 a_l k + k ^ 2) \]

\[= a_l ^ 2 + a_{l + 1} ^ 2 + \cdots + a_{r - 1} ^ 2 + a_r ^ 2 + 2k(a_l + a_{l + 1} + \cdots + a_{r - 1} + a_r) + (r - l + 1) k ^ 2 \]

这样，就只用将区间平方和加上 \(2k(a_l + a_{l + 1} + \cdots + a_{r - 1} + a_r) + (r - l + 1) k ^ 2\) 即可。

#include<bits/stdc++.h>
#define mid ((l + r) >> 1)
#define lchild (root << 1)
#define rchild ((root << 1) + 1)
using namespace std;
const int N = 1e5 + 9;
int n,m;
double a[N];
double sq(double x){
	return x * x;
}
struct node{
	double sum,sq_sum;//区间和，区间平方和 
	double tag;//加法标记 
} t[N << 2];
int len(int l,int r){
	return r - l + 1;
}
bool in_range(int l,int r,int L,int R){
	return L <= l && r <= R;
}
bool out_range(int l,int r,int L,int R){
	return r < L || l > R;
} 
void push_up(int root){
	t[root].sum = t[lchild].sum + t[rchild].sum;
	t[root].sq_sum = t[lchild].sq_sum + t[rchild].sq_sum;
}
void make_tag(int root,int len,double v){
	t[root].tag += v;
	t[root].sq_sum += (sq(v) * len) + (t[root].sum * v * 2);
	t[root].sum += v * len;//这里要注意不要先更新区间合
}
void push_down(int root,int l,int r){
	make_tag(lchild,len(l,mid),t[root].tag);
	make_tag(rchild,len(mid + 1,r),t[root].tag);
	t[root].tag = 0;
}
void build(int root,int l,int r){
	if(l == r){
		t[root].sum = a[l];
		t[root].sq_sum = sq(a[l]);
		return;
	}
	build(lchild,l,mid);
	build(rchild,mid + 1,r);
	push_up(root);
}
void update(int root,int l,int r,int L,int R,double v){
	if(out_range(l,r,L,R))
		return;
	if(in_range(l,r,L,R)){
		make_tag(root,len(l,r),v);
		return;
	}
	push_down(root,l,r);
	update(lchild,l,mid,L,R,v);
	update(rchild,mid + 1,r,L,R,v);
	push_up(root);
}
double query_sum(int root,int l,int r,int L,int R){
	if(out_range(l,r,L,R))
		return 0;
	if(in_range(l,r,L,R))
		return t[root].sum;
	push_down(root,l,r);
	return query_sum(lchild,l,mid,L,R) + query_sum(rchild,mid + 1,r,L,R);
}
double query_sq_sum(int root,int l,int r,int L,int R){
	if(out_range(l,r,L,R))
		return 0;
	if(in_range(l,r,L,R))
		return t[root].sq_sum;
	push_down(root,l,r);
	return query_sq_sum(lchild,l,mid,L,R) + query_sq_sum(rchild,mid + 1,r,L,R);
}
int main(){
	scanf("%d%d", &n, &m);
	for(int i = 1;i <= n;i++)
		scanf("%lf", &a[i]);
	build(1,1,n);
	while(m--){
		int op,l,r;
		scanf("%d%d%d", &op, &l, &r);
		if(op == 1){
			double k;
			scanf("%lf", &k);
			update(1,1,n,l,r,k);
		}
		else if(op == 2){
			double aver = query_sum(1,1,n,l,r) / len(l,r);
			printf("%.4lf\n",aver);
		}
		else if(op == 3){
			double aver = query_sum(1,1,n,l,r) / len(l,r);
			double sq_sum = query_sq_sum(1,1,n,l,r) / len(l,r);
			printf("%.4lf\n",sq_sum - sq(aver));
		}
	}
	return 0;
}

例题 5：区间加区间 sin 和

半道数学题。

前置知识：

\[\sin(a + x) = \sin(a) \cos(x) + \sin(x) \cos(a) \]

\[\cos(a + x) = \cos(a) \cos(x) - \sin(a) \sin(x) \]

看到区间修改想到懒标记，但是发现一个区间的 \(\sin\) 和是无法直接更新的。这就要用到前置知识中的第一条了。

假设一个区间的区间 \(\sin\) 和为 \(\sum_{i = l}^r \sin(a_i)\)，那么一个区间整体加 \(x\) 后区间 \(\sin\) 和就变成：

\[\sum_{i = l}^r \sin(a_i + x) \\ = \sum_{i = l}^r (\sin(a_i) \cos(x) + \sin(x) \cos(a_i)) \\ = \cos(x) \sum_{i = l}^r \sin(a_i) + \sin(x) \sum_{i = l}^r \cos(a_i) \]

\(\sum_{i = l}^r \sin(a_i)\) 是已经求出来了的（不就是原始的区间 \(\sin\) 和吗），我们只用再维护每个区间上的 \(\cos\) 和辅助维护区间 \(\sin\) 和。

那么新的问题就来了：区间 \(\cos\) 和怎么维护？

这就要用到前置知识中的第二条了。

按照同样的方法展开区间整体加 \(x\) 后的区间 \(\cos\) 和：

\[\sum_{i = l}^r \cos(a_i + x) \\ = \sum_{i = l}^r (\cos(a_i) \cos(x) - \sin(a_i) \sin(x)) \\ = \cos(x) \sum_{i = l}^r \cos(a_i) - \sin(x) \sum_{i = l}^r \sin(a_i) \]

这样，我们就发现我们不用维护更多的信息了。

以下是打标记的代码：

void make_tag(int root,int v){
	double sin_tmp = t[root].sin_sum,cos_tmp = t[root].cos_sum;
	t[root].tag += v;
	t[root].sin_sum = sin_tmp * cos(v) + cos_tmp * sin(v);
	t[root].cos_sum = cos_tmp * cos(v) - sin_tmp * sin(v);
}

完整代码：

#include<bits/stdc++.h>
#define int long long
#define mid ((l + r) >> 1)
#define lchild (root << 1)
#define rchild ((root << 1) + 1)
using namespace std;
const int N = 2e5 + 9;
int n,m;
int a[N];
struct node{
	double sin_sum,cos_sum;
	int tag;
} t[N << 2];
bool in_range(int l,int r,int L,int R){
	return L <= l && r <= R;
}
bool out_range(int l,int r,int L,int R){
	return r < L || l > R; 
}
void push_up(int root){
	t[root].sin_sum = t[lchild].sin_sum + t[rchild].sin_sum;
	t[root].cos_sum = t[lchild].cos_sum + t[rchild].cos_sum;
}
void make_tag(int root,int v){
	double sin_tmp = t[root].sin_sum,cos_tmp = t[root].cos_sum;
	t[root].tag += v;
	t[root].sin_sum = sin_tmp * cos(v) + cos_tmp * sin(v);
	t[root].cos_sum = cos_tmp * cos(v) - sin_tmp * sin(v);
}
void push_down(int root){
	if(t[root].tag){
		make_tag(lchild,t[root].tag);
		make_tag(rchild,t[root].tag);
		t[root].tag = 0;
	}
}
void build(int root,int l,int r){
	if(l == r){
		t[root].sin_sum = sin(a[l]);
		t[root].cos_sum = cos(a[l]);
		return;
	}
	build(lchild,l,mid);
	build(rchild,mid + 1,r);
	push_up(root);
}
void update(int root,int l,int r,int L,int R,int v){
	if(out_range(l,r,L,R))
		return;
	if(in_range(l,r,L,R)){
		make_tag(root,v);
		return;
	}
	push_down(root);
	update(lchild,l,mid,L,R,v);
	update(rchild,mid + 1,r,L,R,v);
	push_up(root);
}
double query(int root,int l,int r,int L,int R){
	if(out_range(l,r,L,R))
		return 0;
	if(in_range(l,r,L,R))
		return t[root].sin_sum;
	push_down(root);
	return query(lchild,l,mid,L,R) + query(rchild,mid + 1,r,L,R);
}
signed main(){
	scanf("%lld", &n);
	for(int i = 1;i <= n;i++)
		scanf("%lld", &a[i]);
	build(1,1,n);
	scanf("%lld", &m);
	while(m--){
		int op,l,r;
		scanf("%lld%lld%lld", &op, &l, &r);
		if(op == 1){
			int k;
			scanf("%lld", &k);
			update(1,1,n,l,r,k);
		}
		else if(op == 2)
			printf("%.1lf\n", query(1,1,n,l,r));
	}
	return 0;
}

例题 6：Interval GCD

需要稍微了解一些 \(\gcd\) 的性质。

题解

例题 7：由乃与大母神原型和偶像崇拜

一道线段树 + 哈希的好题。

前置知识：

\[\sum_{i = 1}^n i^2 = 6n(n + 1)(2n + 1) \]

记这个结果为 \(f(n)\)，则进一步得到：

\[\sum_{i = l}^r i^2 = f(r) - f(l - 1) \]

如果一个区间内的数在值域上是连续的（记其中最小值为 \(l\)，最大值为 \(r\)），则一定有 \(f(r) - f(l - 1)\) 等于该区间的所有数的平方和（注意这只是必要条件而非充分条件）。

虽然正确性无法保证，不过可以像哈希判断两个子串是否相等一样将其作为判断的条件。

所以，线段树上就只用维护一个最小值、最大值、以及区间平方和（我用 __int128 玄学爆零了，所以维护模大质数 \(p = 10^9 + 7\) 意义下的区间平方和）。

#include<bits/stdc++.h>
#define mid ((l + r) >> 1)
#define lchild (root << 1)
#define rchild ((root << 1) + 1)
using namespace std;
inline char gc(){
    static char buf[10000005],*t1 = buf,*t2 = buf;
    return t1 == t2 && (t2 = (t1 = buf) + fread(buf,1,1000000,stdin),t1 == t2) ? EOF : *t1++;
}
int read(){
	char c = gc();
	int x = 0;
	while(c < '0' || c > '9')
		c = gc();
	while(c >= '0' && c <= '9'){
		x = (x << 3) + (x << 1) + c - 48;
		c = gc();
	}
	return x;
}
const int N = 5e5 + 9;
const int INF = 2e9,MOD = 1e9 + 7,inv6 = 166666668;
int n,m;
int a[N];
struct node{
	long long sq_sum;
	int Min,Max;
} t[N << 2];
bool in_range(int l,int r,int L,int R){
	return L <= l && r <= R;
}
bool out_range(int l,int r,int L,int R){
	return l > R || r < L;
}
void push_up(int root){
	t[root].sq_sum = (t[lchild].sq_sum + t[rchild].sq_sum) % MOD;
	t[root].Min = min(t[lchild].Min,t[rchild].Min);
	t[root].Max = max(t[lchild].Max,t[rchild].Max);
}
void build(int root,int l,int r){
	if(l == r){
		t[root].Min = t[root].Max = a[l];
		t[root].sq_sum = 1ll * a[l] * a[l] % MOD;
		return;
	}
	build(lchild,l,mid);
	build(rchild,mid + 1,r);
	push_up(root);
}
void update(int root,int l,int r,int pos,int v){
	if(l == r){
		t[root].Min = t[root].Max = v;
		t[root].sq_sum = 1ll * v * v % MOD;
		return;
	}
	if(pos <= mid)
		update(lchild,l,mid,pos,v);
	else
		update(rchild,mid + 1,r,pos,v);
	push_up(root);
}
long long query_sq_sum(int root,int l,int r,int L,int R){
	if(out_range(l,r,L,R))
		return 0;
	if(in_range(l,r,L,R))
		return t[root].sq_sum;
	return (query_sq_sum(lchild,l,mid,L,R) + query_sq_sum(rchild,mid + 1,r,L,R)) % MOD;
}
int query_min(int root,int l,int r,int L,int R){
	if(out_range(l,r,L,R))
		return INF;
	if(in_range(l,r,L,R))
		return t[root].Min;
	return min(query_min(lchild,l,mid,L,R),query_min(rchild,mid + 1,r,L,R));
}
int query_max(int root,int l,int r,int L,int R){
	if(out_range(l,r,L,R))
		return -INF;
	if(in_range(l,r,L,R))
		return t[root].Max;
	return max(query_max(lchild,l,mid,L,R),query_max(rchild,mid + 1,r,L,R));
}
long long _sq_sum_(int v){//1^2+2^2+...v^2
	return 1ll * v * (v + 1) % MOD * (v + v + 1) % MOD * inv6 % MOD;
}
bool query(int l,int r){
	if((_sq_sum_(query_max(1,1,n,l,r)) - _sq_sum_(query_min(1,1,n,l,r) - 1) + MOD) % MOD != query_sq_sum(1,1,n,l,r))
		return false;//不相等就一定不能重排为值域上连续的一段
	return true;
}
int main(){
	ios::sync_with_stdio(false);
	cout.tie(0);
	n = read();m = read();
	for(int i = 1;i <= n;i++)
		a[i] = read();
	build(1,1,n);
	while(m--){
		int op = read();
		if(op == 1){
			int x = read(),y = read();
			update(1,1,n,x,y);
		}
		else if(op == 2){
			int l = read(),r = read();
			cout << (query(l,r) ? "damushen" : "yuanxing") << '\n';
		}
	}
	return 0;
}

例题 8：算术天才⑨与等差数列

上一题的扩展版。

只需要知道：

\[\sum_{i = 0} ^ {r - l} (x + ki) = (r - l + 1)x ^ 2 + kx(r - l)(r - l + 1) + k ^ 2 \sum_{i = 0}^{r - l}i ^ 2 \]

证明方法就是直接展开。

这就是一个公差为 \(k\)，首项为 \(x\)，长度为 \(r - l + 1\) 的等差数列之和，和上一题一样，我们用这个值与 \(\sum_{i = l}^r a_i^2\) 在 \(\bmod (10^9 + 7)\) 的意义下比较。

最后的 \(k ^ 2 \sum_{i = 0}^{r - l}i ^ 2\) 计算方法和上一题一样。

#include<bits/stdc++.h>
#define int long long
#define mid ((l + r) >> 1)
#define lchild (root << 1)
#define rchild ((root << 1) + 1)
using namespace std;
inline char gc(){
    static char buf[10000005],*t1 = buf,*t2 = buf;
    return t1 == t2 && (t2 = (t1 = buf) + fread(buf,1,1000000,stdin),t1 == t2) ? EOF : *t1++;
}
int read(){
	#define gc() getchar()
	char c = gc();
	int x = 0;
	while(c < '0' || c > '9')
		c = gc();
	while(c >= '0' && c <= '9'){
		x = (x << 3) + (x << 1) + c - 48;
		c = gc();
	}
	return x;
}
const int N = 3e5 + 9;
const int INF = 2e9,MOD = 1e9 + 7,inv6 = 166666668;
int n,m;
int a[N];
struct node{
	int sq_sum;
	int Min;
} t[N << 2];
bool in_range(int l,int r,int L,int R){
	return L <= l && r <= R;
}
bool out_range(int l,int r,int L,int R){
	return l > R || r < L;
}
void push_up(int root){
	t[root].sq_sum = (t[lchild].sq_sum + t[rchild].sq_sum) % MOD;
	t[root].Min = min(t[lchild].Min,t[rchild].Min);
}
void build(int root,int l,int r){
	if(l == r){
		t[root].Min = a[l];
		t[root].sq_sum = 1ll * a[l] * a[l] % MOD;
		return;
	}
	build(lchild,l,mid);
	build(rchild,mid + 1,r);
	push_up(root);
}
void update(int root,int l,int r,int pos,int v){
	if(l == r){
		t[root].Min = v;
		t[root].sq_sum = 1ll * v * v % MOD;
		return;
	}
	if(pos <= mid)
		update(lchild,l,mid,pos,v);
	else
		update(rchild,mid + 1,r,pos,v);
	push_up(root);
}
int query_sq_sum(int root,int l,int r,int L,int R){
	if(out_range(l,r,L,R))
		return 0;
	if(in_range(l,r,L,R))
		return t[root].sq_sum;
	return (query_sq_sum(lchild,l,mid,L,R) + query_sq_sum(rchild,mid + 1,r,L,R)) % MOD;
}
int query_min(int root,int l,int r,int L,int R){
	if(out_range(l,r,L,R))
		return INF;
	if(in_range(l,r,L,R))
		return t[root].Min;
	return min(query_min(lchild,l,mid,L,R),query_min(rchild,mid + 1,r,L,R));
}
int _sq_sum_(int v){//1^2+2^2+...v^2
	return v * (v + 1) % MOD * (v + v + 1) % MOD * inv6 % MOD;
}
bool query(int l,int r,int k){
	int Min = query_min(1,1,n,l,r);
	int val = ((r - l + 1) * Min % MOD * Min % MOD
				+k * Min % MOD * (r - l) % MOD * (r - l + 1) % MOD
				+k * k % MOD * _sq_sum_(r - l) % MOD) % MOD;
	if((val + MOD) % MOD != query_sq_sum(1,1,n,l,r))
		return false;
	return true;
}
int cnt;
signed main(){
	ios::sync_with_stdio(false);
	cout.tie(0);
	n = read();m = read();
	for(int i = 1;i <= n;i++)
		a[i] = read();
	build(1,1,n);
	while(m--){
		int op = read();
		if(op == 1){
			int x = read() ^ cnt,y = read() ^ cnt;
			update(1,1,n,x,y);
		}
		else if(op == 2){
			int l = read() ^ cnt,r = read() ^ cnt,k = read() ^ cnt;
			if(query(l,r,k)){
				cout << "Yes\n";
				cnt++;
			}
			else
				cout << "No\n";
		}
	}
	return 0;
}

【2】更多线段树的操作

【2.1】线段树与多标记

有些问题有多种区间修改，这就需要维护多个懒标记。并且在执行一种操作的时候可能要更新多个懒标记，这就需要在 push_down 时注意下传顺序等细节了。

例题 1：线段树 2

区间加 + 区间乘 + 区间求和。

这里区间加和区间乘显然不能共用一个标记，所以使用 tag1 代表区间加的标记，tag2 代表区间乘的标记（tag2 初值要设为 \(1\)）。

对于区间加操作，更新懒标记的方式是一样的。但是区间乘难道只是更新区间乘标记这么简单吗？

显然没有这么简单。

如果只乘了乘法标记，那么就会发现：

假入序列长度为 \(2\)，初值均为 \(0\)，我先整体加 \(11\)，再整体乘 \(45\)，这样根的加法标记是 \(11\)，乘法标记是 \(45\)，那你是先传加法标记还是乘法标记呢？

如果先传乘法标记，那么会得到左右子节点的值均为 \(11\)，但实际应为 \(495\)；

如果先传加法标记，也可以构造出这么一个反例：

序列长度为 \(2\)，初值均为 \(0\)，我先整体加 \(11\)，再整体乘 \(4\)，再整体加 \(5\)，再整体乘 \(14\),这样根的加法标记是 \(16\)，乘法标记是 \(56\)，会得到左右子节点的值均为 \(896\)，但实际应为 \(686\)。

事实上，应该在更新乘法标记的时候同时更新加法标记。

以下是打标记和下传标记的代码：

void make_tag(int root,int len,int v,int op){
	if(op == 1){//区间乘操作
		(t[root].sum *= v) %= p;
		(t[root].tag1 *= v) %= p;
		(t[root].tag2 *= v) %= p;
	}
	else if(op == 2){
		(t[root].sum += len * v) %= p;
		(t[root].tag1 += v) %= p;
	}
}

void push_down(int root,int l,int r){
	if(t[root].tag2 != 1){//要先传乘法标记再传加法标记
		make_tag(lchild,len(l,mid),t[root].tag2,1);
		make_tag(rchild,len(mid + 1,r),t[root].tag2,1);
		t[root].tag2 = 1;
	}
	if(t[root].tag1){
		make_tag(lchild,len(l,mid),t[root].tag1,2);
		make_tag(rchild,len(mid + 1,r),t[root].tag1,2);
		t[root].tag1 = 0;
	}
}

完整代码：

#include<bits/stdc++.h>
#define int long long
#define mid ((l + r) >> 1)
#define lchild (root << 1)
#define rchild ((root << 1) + 1)
using namespace std;
const int N = 1e5 + 9;
int n,m,p;
int a[N];
struct node{
	int sum;//区间和
	int tag1,tag2 = 1;//加法标记，乘法标记
} t[N << 2];
int len(int l,int r){
	return r - l + 1;
}

bool in_range(int l,int r,int L,int R){
	return L <= l && r <= R;
}
bool out_range(int l,int r,int L,int R){
	return l > R || r < L;
}

void push_up(int root){
	t[root].sum = (t[lchild].sum + t[rchild].sum) % p;
}

void make_tag(int root,int len,int v,int op){
	if(op == 1){//区间乘操作
		(t[root].sum *= v) %= p;
		(t[root].tag1 *= v) %= p;
		(t[root].tag2 *= v) %= p;
	}
	else if(op == 2){
		(t[root].sum += len * v) %= p;
		(t[root].tag1 += v) %= p;
	}
}

void push_down(int root,int l,int r){
	if(t[root].tag2 != 1){//要先传乘法标记再传加法标记
		make_tag(lchild,len(l,mid),t[root].tag2,1);
		make_tag(rchild,len(mid + 1,r),t[root].tag2,1);
		t[root].tag2 = 1;
	}
	if(t[root].tag1){
		make_tag(lchild,len(l,mid),t[root].tag1,2);
		make_tag(rchild,len(mid + 1,r),t[root].tag1,2);
		t[root].tag1 = 0;
	}
}

void build(int root,int l,int r){
	if(l == r){
		t[root].sum = a[l] % p;
		return;
	}
	build(lchild,l,mid);
	build(rchild,mid + 1,r);
	push_up(root);
}
void update(int root,int l,int r,int L,int R,int v,int op){
	if(out_range(l,r,L,R))
		return;
	if(in_range(l,r,L,R)){
		make_tag(root,len(l,r),v,op);
		return;
	}
	push_down(root,l,r);
	update(lchild,l,mid,L,R,v,op);
	update(rchild,mid + 1,r,L,R,v,op);
	push_up(root);
}
int query(int root,int l,int r,int L,int R){
	if(out_range(l,r,L,R))
		return 0;
	if(in_range(l,r,L,R))
		return t[root].sum;
	push_down(root,l,r);
	return (query(lchild,l,mid,L,R) + query(rchild,mid + 1,r,L,R)) % p;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> n >> m >> p;
	for(int i = 1;i <= n;i++)
		cin >> a[i];
	build(1,1,n);
	while(m--){
		int op,l,r;
		cin >> op >> l >> r;
		if(op == 1 || op == 2){
			int k;
			cin >> k;
			update(1,1,n,l,r,k,op);
		}
		else if(op == 3)
			cout << query(1,1,n,l,r) << '\n';
	}
	return 0;
}

例题 2：扶苏的问题

区间推平 + 区间加 + 区间最值。

显然，区间推平会使一个区间的加法标记失效，所以区间推平既要修改区间推平标记，又要将加法标记清空。

但区间加操作不能直接清空区间推平标记，并且如果区间推平标记不为空，我们就得在区间推平标记上加而非在区间加标记上加。这是因为在下传标记的时候肯定是先下传区间推平标记（否则区间加标记传了也会被覆盖，不如不传）。

在【1.2.2】中提到，可以用 \(\inf\) 来表示区间推平标记为空，为了偷懒（雾），\(\inf\) 就直接取 \(10^{18}\) 了。

以下是打标记和下传标记的代码：

void make_tag(int root,int v,int op){
	if(op == 1){
		t[root].Max = v;
		t[root].tag1 = v;
		t[root].tag2 = 0;
	}
	else if(op == 2){
		t[root].Max += v;
		if(t[root].tag1 != INF)
			t[root].tag1 += v;
		else
			t[root].tag2 += v; 
	}
}
void push_down(int root,int l,int r){
	if(t[root].tag1 != INF){
		make_tag(lchild,t[root].tag1,1);
		make_tag(rchild,t[root].tag1,1);
		t[root].tag1 = INF;
	}
	else{
		make_tag(lchild,t[root].tag2,2);
		make_tag(rchild,t[root].tag2,2);
		t[root].tag2 = 0;
	}
}

完整代码：

#include<bits/stdc++.h>
#define int long long
#define mid ((l + r) >> 1)
#define lchild (root << 1)
#define rchild ((root << 1) + 1)
using namespace std;
const int N = 1e6 + 9,INF = 1e18;
int n,m;
int a[N];
struct node{
	int Max;//区间最大值 
	int tag1 = INF,tag2;//区间修改标记，区间加标记 
} t[N << 2];

bool in_range(int l,int r,int L,int R){
	return L <= l && r <= R;
}
bool out_range(int l,int r,int L,int R){
	return l > R || r < L;
}

void push_up(int root){
	t[root].Max = max(t[lchild].Max,t[rchild].Max);
}

void make_tag(int root,int v,int op){
	if(op == 1){
		t[root].Max = v;
		t[root].tag1 = v;
		t[root].tag2 = 0;
	}
	else if(op == 2){
		t[root].Max += v;
		if(t[root].tag1 != INF)
			t[root].tag1 += v;
		else
			t[root].tag2 += v; 
	}
}
void push_down(int root,int l,int r){
	if(t[root].tag1 != INF){
		make_tag(lchild,t[root].tag1,1);
		make_tag(rchild,t[root].tag1,1);
		t[root].tag1 = INF;
	}
	else{
		make_tag(lchild,t[root].tag2,2);
		make_tag(rchild,t[root].tag2,2);
		t[root].tag2 = 0;
	}
}


void build(int root,int l,int r){
	if(l == r){
		t[root].Max = a[l];
		return;
	}
	build(lchild,l,mid);
	build(rchild,mid + 1,r);
	push_up(root);
}
void update(int root,int l,int r,int L,int R,int v,int op){
	if(out_range(l,r,L,R))
		return;
	if(in_range(l,r,L,R)){
		make_tag(root,v,op);
		return;
	}
	push_down(root,l,r);
	update(lchild,l,mid,L,R,v,op);
	update(rchild,mid + 1,r,L,R,v,op);
	push_up(root);
}
int query(int root,int l,int r,int L,int R){
	if(out_range(l,r,L,R))
		return -INF;
	if(in_range(l,r,L,R))
		return t[root].Max;
	push_down(root,l,r);
	return max(query(lchild,l,mid,L,R),query(rchild,mid + 1,r,L,R));
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> n >> m;
	for(int i = 1;i <= n;i++)
		cin >> a[i];
	build(1,1,n);
	while(m--){
		int op,l,r;
		cin >> op >> l >> r;
		if(op == 1 || op == 2){
			int k;
			cin >> k;
			update(1,1,n,l,r,k,op);
		}
		else
			cout << query(1,1,n,l,r) << '\n';
	}
	return 0;
}

【2.2】线段树与“剪枝”

学名应该叫势能线段树，但我不会势能分析，只能认为这是一种强力的“剪枝”了。

有些操作（例如区间开根），无法直接更新区间值，也就无法打懒标记，必须暴力更新叶节点。这种题目也有保证复杂度的方法。

例题 1：上帝造题的七分钟 2 / 花神游历各国

区间开根下取整 + 区间求和板子。

区间开根下取整无法直接修改区间和，必须暴力更新叶节点，每次复杂度最坏 \(O(n)\)。

但是，针对这种题目，有一个技巧：维护一些额外的信息，使得可以判断对一个区间的修改是“无效的”（不会更新信息）。

对于本题，这种修改无效的区间就是全 \(1\) 的区间。

判断一个区间是否全 \(1\) 很简单。因为本题中数最小只会变为 \(1\)，所以每个节点额外维护区间最大值，当这个值为 \(1\) 说明当前节点对应的区间的修改是“无效”的，直接返回即可。

另外，因为本题中每个数小于 \(10^{12}\)，可以通过手动计算得出每个数至多被修改 \(6 \sim 7\) 次就会变成 \(1\)，所以总复杂度可以保证 \(O(m \log n)\)。

#include<bits/stdc++.h>
#define lchild (root << 1)
#define rchild ((root << 1) + 1)
#define mid ((l + r) >> 1)
using namespace std;
typedef long long ll;
const int N = 1e5 + 9;
int n,m;
ll a[N];
struct node{
	ll sum,Max;
} t[N << 2];
bool in_range(int l,int r,int L,int R){
	return L <= l && r <= R;
}
bool out_range(int l,int r,int L,int R){
	return L > r || l > R;
}
void push_up(int root){
	t[root].sum = t[lchild].sum + t[rchild].sum;
	t[root].Max = max(t[lchild].Max,t[rchild].Max);
}
void build(int root,int l,int r){
	if(l == r){
		t[root].sum = t[root].Max = a[l];
		return;
	}
	build(lchild,l,mid);
	build(rchild,mid + 1,r);
	push_up(root);
}
void update(int root,int l,int r,int L,int R){
	if(t[root].Max == 1 || out_range(l,r,L,R))//剪枝在这里
		return;
	if(l == r){//到达叶子节点，暴力修改
		t[root].sum = (ll)sqrt(t[root].sum);
		t[root].Max = (ll)sqrt(t[root].Max);
		return;
	}
	update(lchild,l,mid,L,R);
	update(rchild,mid + 1,r,L,R);
	push_up(root);
}
ll query(int root,int l,int r,int L,int R){
	if(in_range(l,r,L,R))
		return t[root].sum;
	if(!out_range(l,r,L,R))
		return query(lchild,l,mid,L,R) + query(rchild,mid + 1,r,L,R);
	return 0;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> n;
	for(int i = 1;i <= n;i++)
		cin >> a[i];
	build(1,1,n);
	cin >> m;
	for(int i = 1;i <= m;i++){
		int k,l,r;
		cin >> k >> l >> r;
		if(l > r)
			swap(l,r);
		if(k == 0)
			update(1,1,n,l,r);
		else
			cout << query(1,1,n,l,r) << '\n';
	}
	return 0;
}

例题 2：The Child and Sequence

区间取模 + 单点修改 + 区间求和。

技巧和上一题一模一样，如果一个区间内的数都小于模数，那么对该区间的修改是无效的。

因此还是记录区间最值，代码如下：

#include<bits/stdc++.h>
#define mid ((l + r) >> 1)
#define lchild (root << 1)
#define rchild ((root << 1) + 1)
using namespace std;
typedef long long ll;
const int N = 1e5 + 9;
int n,m;
ll a[N];
struct node{
	ll sum,Max;
} t[N << 2];
bool in_range(int l,int r,int L,int R){
	return L <= l && r <= R;
}
bool out_range(int l,int r,int L,int R){
	return l > R || r < L;
}
void push_up(int root){
	t[root].sum = t[lchild].sum + t[rchild].sum;
	t[root].Max = max(t[lchild].Max,t[rchild].Max);
}
void build(int root,int l,int r){
	if(l == r){
		t[root].sum = t[root].Max = a[l];
		return;
	}
	build(lchild,l,mid);
	build(rchild,mid + 1,r);
	push_up(root);
}
void update1(int root,int l,int r,int L,int R,int MOD){
	if(t[root].Max < MOD || out_range(l,r,L,R))//剪枝在这里
		return;
	if(l == r){//到达叶子节点，暴力修改
		t[root].sum = t[root].sum % MOD;
		t[root].Max = t[root].Max % MOD;
		return;
	}
	update1(lchild,l,mid,L,R,MOD);
	update1(rchild,mid + 1,r,L,R,MOD);
	push_up(root);
}
void update2(int root,int l,int r,int pos,int x){
	if(l == r){
		t[root].sum = t[root].Max = x;
		return;
	}
	if(pos <= mid)
		update2(lchild,l,mid,pos,x);
	else
		update2(rchild,mid + 1,r,pos,x);
	push_up(root);
}
ll query(int root,int l,int r,int L,int R){
	if(in_range(l,r,L,R))
		return t[root].sum;
	if(!out_range(l,r,L,R))
		return query(lchild,l,mid,L,R) + query(rchild,mid + 1,r,L,R);
	return 0;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> n >> m;
	for(int i = 1;i <= n;i++)
		cin >> a[i];
	build(1,1,n);
	for(int i = 1;i <= m;i++){
		int k,l,r,x;
		cin >> k;
		if(k == 1){
			cin >> l >> r;
			cout << query(1,1,n,l,r) << '\n';
		}
		if(k == 2){
			cin >> l >> r >> x;
			update1(1,1,n,l,r,x);
		}
		if(k == 3){
			cin >> l >> x;
			update2(1,1,n,l,x);
		}
	}
	return 0;
}

一个数如被修改一次（要发生变化）后至少会减半，所以复杂度为 \(O(n \log n \log V)\)。

例题 3：TEST_69

区间 GCD 修改 + 区间求和。

判断什么样的区间修改是无效的。如果一个区间 \([l,r]\) 的修改是无效的，那么区间内的 \(a_i\) 满足 \(a_i = \gcd(a_i,x)\)，进一步可得 \(a_i | x\)。

也就是说，如果一个区间 \([l,r]\) 的修改是无效的，则 \(a_l | x,a_{l + 1} | x,\cdots a_{r - 1} | x,a_r | x\)，这等价于 \(x\) 是 \(a_l,a_{l + 1},\cdots a_{r - 1},a_r\) 的公倍数。

由最小公倍数的性质，这进一步等价于 \(\operatorname{LCM}(a_l,a_{l + 1},\cdots,a_{r - 1},a_r) | x\)。

所以，我们只需要维护区间最小公倍数即可。又因为对于一个数，如果被修改一次产生了变动，这个数至少会减半，所以一个数至多被修改 \(\lceil \log 10^{18} \rceil = 61\) 次，复杂度也可以保证 \(O(m \log n)\)。

另外，一个区间的 LCM 有爆 long long 的风险，不过，观察无效修改的条件可以看出：LCM 必须小于 \(x\)，也即小于 \(10^{18}\)。所以，发现区间 LCM 值超过 \(10^{18}\) 时，直接标记 LCM 为 \(-1\)，在判断是否整除的时候特判 LCM 是否小于 \(0\) 即可，合并的时候判一下左右子节点的 LCM 是否有为 \(-1\) 的，以及左右子节点的 LCM 相乘除以左右子节点 LCM 的最大公因数是否超过 \(10^{18}\)（这条判定可以转化为除法判定避免爆 long long，详见代码）。

#include<bits/stdc++.h>
#define int long long
#define mid ((l + r) >> 1)
#define lchild (root << 1)
#define rchild ((root << 1) + 1)
using namespace std;
const int N = 2e5 + 9,INF = 1e18;
int a[N];
int GCD(int x,int y){
	return y ? GCD(y,x % y) : x;
}
struct node{
	int LCM;
	unsigned sum;
} t[N << 2];
bool in_range(int l,int r,int L,int R){
	return L <= l && r <= R;
}
bool out_range(int l,int r,int L,int R){
	return l > R || r < L;
}
void pushup(int root) {
	if(t[lchild].LCM == -1 || t[rchild].LCM == -1)
		t[root].LCM = -1;
	else{
		int gcd = GCD(t[lchild].LCM, t[rchild].LCM);
		int x = t[lchild].LCM / gcd;
		if (t[rchild].LCM > INF / x)
			t[root].LCM = -1;
		else
			t[root].LCM = x * t[rchild].LCM;
	}
	t[root].sum = t[lchild].sum + t[rchild].sum;
}
void build(int root,int l,int r){
	if(l == r){
		t[root].LCM = a[l];
		t[root].sum = a[l];
		return;
	}
	build(lchild,l,mid);
	build(rchild,mid + 1,r);
	pushup(root);
}
unsigned query(int root,int l,int r,int L,int R) {
	if(out_range(l,r,L,R))
		return 0;
	if(in_range(l,r,L,R))
		return t[root].sum;
	return query(lchild,l,mid,L,R) + query(rchild,mid + 1,r,L,R);
}
void update(int root,int l,int r,int L,int R,int x) {
	if ((t[root].LCM != -1 && !(x % t[root].LCM)) || out_range(l,r,L,R))//剪枝在这里
		return;
	if(l == r){//到达叶节点，暴力修改
		a[l] = GCD(a[l],x);
		t[root].LCM = a[l];
		t[root].sum = a[l];
		return;
	}
	update(lchild,l,mid,L,R,x);
	update(rchild,mid + 1,r,L,R,x);
	pushup(root); 
}
int n,m;
int op,l,r,x;
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> n >> m;
	for (int i = 1;i <= n;i++)
		cin >> a[i];
	build(1,1,n);
	while(m--){
		cin >> op >> l >> r;
		if(op == 1){
			cin >> x;
			update(1,1,n,l,r,x);
		}
		else
			cout << query(1,1,n,l,r) << '\n';
	}
	return 0;
}

和上一题一样，一个数如被修改一次（要发生变化）后至少会减半，所以复杂度为 \(O(n \log n \log V)\)。

【2.3】维护更多信息辅助合并

有些信息，例如最大子段和，无法通过左区间的最大子段和和右区间的最大子段和推出当前区间的最大子段和。

例如，序列 \(\{-1,1\}\)、\(\{1,-1\}\) 的最大子段和都是 \(1\)，但序列 \(\{-1,1,1,-1\}\) 的最大子段和是 \(2\)，序列 \(\{-1,1,-1,1\}\) 的最大子段和是 \(1\)。

例题 1：小白逛公园

单点修改 + 最大子段和板子。

温馨提示：本题的最大子段和不能是空序列，所以不保证最大子段和大于 \(0\)。

对于一个序列的子段和，有三种情况：

  1. 该子段在左半区间。

  2. 该子段在右半区间。

  3. 该子段介于左右半区间。

也就对应一个区间的最大子段和由三部分合并得到：

  1. 左半区间的最大子段和。

  2. 右半区间的最大子段和。

  3. 左半区间的最大后缀和加右半区间的最大子段和。

那这也意味着我们要维护区间最大前缀和及最大后缀和。

区间最大前缀和由两部分合并得到：

  1. 左半区间的最大前缀和。

  2. 左半区间的区间和加上右半区间的最大前缀和。

同理，区间最大后缀和也有两部分得到：

  1. 右半区间的最大后缀和。

  2. 右半区间的区间和加上左半区间的最大后缀和。

对于叶节点，其区间和、最大子段和、最大前缀和、最大后缀和都是该位置的值。

struct node{
	int sum,val;//区间和、区间最大子段和 
	int lsum,rsum;//前缀最大和、后缀最大和 
} t[N << 2];
void push_up(int root){
	t[root].sum = t[lchild].sum + t[rchild].sum; 
	t[root].val = max(max(t[lchild].val,t[rchild].val),t[lchild].rsum + t[rchild].lsum);
	t[root].lsum = max(t[lchild].lsum,t[lchild].sum + t[rchild].lsum);
	t[root].rsum = max(t[rchild].rsum,t[rchild].sum + t[lchild].rsum);
}

不只是 push_up 的时候需要讨论这 \(4\) 种情况，在查询的时候也要用这种合并方式，代码如下：

node query(int root,int l,int r,int L,int R){
	if(out_range(l,r,L,R))
		return (node){-INF,-INF,-INF,-INF};
	if(in_range(l,r,L,R))
		return t[root];
	node ql = query(lchild,l,mid,L,R),qr = query(rchild,mid + 1,r,L,R);
	return (node){
		ql.sum + qr.sum,
		max(max(ql.val,qr.val),ql.rsum + qr.lsum),
		max(ql.lsum,ql.sum + qr.lsum),
		max(qr.rsum,qr.sum + ql.rsum)
	};
}

完整代码如下：

#include<bits/stdc++.h>
#define int long long
#define mid ((l + r) >> 1)
#define lchild (root << 1)
#define rchild ((root << 1) + 1)
using namespace std;
const int N = 5e5 + 9,INF = 1e9;
int n,m;
int a[N];
struct node{
	int sum,val;//区间和、区间最大子段和 
	int lsum,rsum;//前缀最大和、后缀最大和 
} t[N << 2];
bool in_range(int l,int r,int L,int R){
	return L <= l && r <= R;
}
bool out_range(int l,int r,int L,int R){
	return r < L || l > R;
}
void push_up(int root){
	t[root].sum = t[lchild].sum + t[rchild].sum; 
	t[root].val = max(max(t[lchild].val,t[rchild].val),t[lchild].rsum + t[rchild].lsum);
	t[root].lsum = max(t[lchild].lsum,t[lchild].sum + t[rchild].lsum);
	t[root].rsum = max(t[rchild].rsum,t[rchild].sum + t[lchild].rsum);
}
void build(int root,int l,int r){
	if(l == r){
		t[root].sum = t[root].val = t[root].lsum = t[root].rsum = a[l];//该题的最大子段和不能不选，所以单位长度的区间最大子段和为该位置上的值 
		return;
	}
	build(lchild,l,mid);
	build(rchild,mid + 1,r);
	push_up(root);
}
node query(int root,int l,int r,int L,int R){
	if(out_range(l,r,L,R))
		return (node){-INF,-INF,-INF,-INF};
	if(in_range(l,r,L,R))
		return t[root];
	node ql = query(lchild,l,mid,L,R),qr = query(rchild,mid + 1,r,L,R);
	return (node){
		ql.sum + qr.sum,
		max(max(ql.val,qr.val),ql.rsum + qr.lsum),
		max(ql.lsum,ql.sum + qr.lsum),
		max(qr.rsum,qr.sum + ql.rsum)
	};
}
void update(int root,int l,int r,int pos,int v){
	if(l == r){
		t[root].sum = t[root].val = t[root].lsum = t[root].rsum = v;
		return;
	}
	if(pos <= mid)
		update(lchild,l,mid,pos,v);
	else
		update(rchild,mid + 1,r,pos,v);
	push_up(root);
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> n >> m;
	for(int i = 1;i <= n;i++)
		cin >> a[i];
	build(1,1,n);
	while(m--){
		int op;
		cin >> op;
		if(op == 1){
			int l,r;
			cin >> l >> r;
			if(l > r)
				swap(l,r);
			cout << query(1,1,n,l,r).val << '\n'; 
		}
		else if(op == 2){
			int pos,v;
			cin >> pos >> v;
			update(1,1,n,pos,v);
		}
	}
	return 0;
}

例题 2：Hotel G

对于第一个操作，不难发现其具有分治的特点。如果左半区间的最长的连续空房数量达到了 \(x\)，那么就直接进入左半区间查找；如果区间长度为 \(1\) 了，那么直接返回这个位置。

我们先不考虑答案区间如果介于左半区间和右半区间之间或完全包含在右半区间的情况，先考虑“最长的连续空房数量”这个东西怎么维护。

维护方法和上一题最大子段和的方法一模一样，下面讨论其余三个辅助的值如何维护：

  1. 本题中“区间和”就等于区间长度，所以不用单独维护。

  2. “前缀最大和”和上一题略有不同，仅当左半区间“前缀最大和”等于左半区间长度时，“前缀最大和”才能取左半区间长度加右半区间“前缀最大和”，否则就只能取左半区间“前缀最大和”（入住房间肯定必须是连续的）。

  3. “后缀最大和”类似，仅当右半区间“后缀最大和”等于右半区间长度时，“后缀最大和”才能取右半区间长度加左半区间“后缀最大和”，否则就只能取右半区间“后缀最大和”。

再回到刚才遗留的操作 \(1\) 的问题：如果答案区间介于左半区间和右半区间之间或完全包含在右半区间怎么办？

其实也简单，如果答案区间介于左半区间和右半区间之间（左半区间最大后缀和加右半区间最大前缀和达到 \(x\)），那么答案的左端点就是 \(mid - 左半区间后缀最大和 + 1\)（请自行理解），否则就进入右半区间查找。

特别的，如果根节点的“最大子段和”小于 \(x\)，直接输出 \(0\)。

查询讲完了，入住和退房本质就是区间推平操作，维护一个懒标记即可，具体参见代码：

#include<bits/stdc++.h>
#define mid ((l + r) >> 1)
#define lchild (root << 1)
#define rchild ((root << 1) + 1)
using namespace std;

const int N = 5e4 + 9;
int n,m;

struct node{
	int val;//区间最大连续空房数 
	int lsum,rsum;//前缀最大连续空房数，后缀最大连续空房数 
	int tag;//懒标记：0代表无操作，1代表整体入住，2代表整体退房 
} t[N << 2];

int len(int l,int r){
	return r - l + 1;
}

bool in_range(int l,int r,int L,int R){//[l,r]是否在修改/查询区间[L,R]中 
	return L <= l && r <= R;
}
bool out_range(int l,int r,int L,int R){//[l,r]是否与修改/查询区间[L,R]无交集 
	return l > R || r < L;
}

void push_up(int root,int l,int r){
	t[root].val = max(max(t[lchild].val,t[rchild].val),t[lchild].rsum + t[rchild].lsum);
	t[root].lsum = ((t[lchild].lsum == len(l,mid)) ? len(l,mid) + t[rchild].lsum : t[lchild].lsum);
	t[root].rsum = ((t[rchild].rsum == len(mid + 1,r)) ? len(mid + 1,r) + t[lchild].rsum : t[rchild].rsum);
}

void make_tag(int root,int len,int type){
	t[root].tag = type;
	if(type == 1)
		t[root].val = t[root].lsum = t[root].rsum = 0;
	else if(type == 2)
		t[root].val = t[root].lsum = t[root].rsum = len;
}
void push_down(int root,int l,int r){
	if(t[root].tag){
		make_tag(lchild,len(l,mid),t[root].tag);
		make_tag(rchild,len(mid + 1,r),t[root].tag);
		t[root].tag = 0;
	}
}

void build(int root,int l,int r){
	if(l == r){
		t[root].val = t[root].lsum = t[root].rsum = 1;
		return;
	}
	build(lchild,l,mid);
	build(rchild,mid + 1,r);
	push_up(root,l,r);
}

void update(int root,int l,int r,int L,int R,int type){
	if(out_range(l,r,L,R))
		return;
	if(in_range(l,r,L,R)){
		make_tag(root,len(l,r),type);
		return;
	}
	push_down(root,l,r);
	update(lchild,l,mid,L,R,type);
	update(rchild,mid + 1,r,L,R,type);
	push_up(root,l,r);
}

int query(int root,int l,int r,int v){
	if(l == r)
		return l;
	push_down(root,l,r);
	if(t[lchild].val >= v)
		return query(lchild,l,mid,v);
	else if(t[lchild].rsum + t[rchild].lsum >= v)
		return mid - t[lchild].rsum + 1;
	else if(t[rchild].val >= v) 
		return query(rchild,mid + 1,r,v);
	return 0;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> n >> m;
	build(1,1,n);
	while(m--){
		int op,l,r,len;
		cin >> op;
		if(op == 1){
			cin >> len;
			if(t[1].val >= len){
				l = query(1,1,n,len);
				cout << l << '\n';
				r = l + len - 1;
				update(1,1,n,l,r,1);
			}
			else
				cout << "0\n";
		}
		else if(op == 2){
			cin >> l >> len;
			r = l + len - 1;
			update(1,1,n,l,r,2);
		}
	}
	return 0; 
}

例题 3：纵使日薄西山

这是一道非常复杂的线段树题目（不愧是 Ynoi），主要复杂在 push_up 部分，也需要通过额外的信息得到我们要求的区间信息。

题解很长，就放这了：

题解

【3】更多线段树

【3.1】权值线段树

权值线段树是一种特殊的线段树，

假设有序列 \(a\)，\(b\) 是 \(a\) 的计数器，称 \(b\) 为 \(a\) 的权值序列，则对 \(b\) 构造的线段树称为权值线段树。

例如，\(\{1,1,4,5,1,4,1,9,1,9,8,1\}\) 的权值序列为 \(\{6,0,0,2,1,0,0,1,1\}\)。

权值线段树在处理大小关系相关的问题时很有效，但当值域较大时，需要先离散化。在一些无法离散化的题目中需使用下文提到的动态开点。

和普通线段树相比，权值线段树每个结点的权值一定是非负的，所以权值线段树的查询部分可稍作修改：当当前节点权值为 \(0\) 时，可直接返回 \(0\)，因为当前节点的所有子节点权值也一定为 \(0\)（数的出现次数不可能为负）。

以下是权值线段树的修改和查询代码：

void update(int root,int l,int r,int v,int k){//将v的出现次数加k
	if(l == r){
		t[root].sum += k;
		return;
	}
	if(v <= mid)
		update(lchild,l,mid,v,1);
	else
		update(rchild,mid + 1,r,v,1);
	push_up(root);
}

int query(int root,int l,int r,int v){//查询当前序列有多少个不超过v的数，即求计数器[1,v]的和 
	if(!t[root].sum)//权值线段树特有的写法（sum一定不为负，所以一个区间和为0说明整个区间都是0） 
		return 0;
	if(l == r)
		return t[root].sum;
	if(v <= mid)
		return query(lchild,l,mid,v);
	else
		return t[lchild].sum + query(rchild,mid + 1,r,v);
}

例题 1：逆序对

逆序对的个数与数的具体值无关，只与数的大小关系有关，所以先将数列离散化。

对于一个数 \(a_i\)，可以与 \(a_i\) 构成逆序对的数 \(a_j\) 肯定满足 \(j < i\) 且 \(a_j > a_i\)。统计满足条件的数方法很多，以下是一种可行的方案：

每遍历到一个数 \(a_i\)，立刻在权值线段树上更新 \(a_i\)，此时的权值线段树维护的是 \(\{a_1,a_2,\cdots,a_{i - 1},a_i\}\) 对应的权值序列，在这当中能与 \(a_i\) 形成逆序对的就是其中大于 \(a_i\) 的数。而上文的 query 函数实现的是查询不大于 \(a_i\) 的数，记这个结果为 \(q\)，则大于 \(a_i\) 的数就是 \(i - q\)（权值线段树只维护了前 \(i\) 个数），将答案加上 \(i - q\) 即可。

#include<bits/stdc++.h>
#define mid ((l + r) >> 1)
#define lchild (root << 1)
#define rchild ((root << 1) + 1)
using namespace std;
const int N = 5e5 + 9;
int n;
int a[N],tmp[N],top;
struct node{
	int sum;
} t[N << 2];
void push_up(int root){
	t[root].sum = t[lchild].sum + t[rchild].sum;
}
long long ans; 
void update(int root,int l,int r,int v,int k){//将v的出现次数加k
	if(l == r){
		t[root].sum += k;
		return;
	}
	if(v <= mid)
		update(lchild,l,mid,v,1);
	else
		update(rchild,mid + 1,r,v,1);
	push_up(root);
}
int query(int root,int l,int r,int v){//查询当前序列有多少个不超过v的数，即求计数器[1,v]的和 
	if(!t[root].sum)//权值线段树特有的写法（sum一定不为负，所以一个区间和为0说明整个区间都是0） 
		return 0;
	if(l == r)
		return t[root].sum;
	if(v <= mid)
		return query(lchild,l,mid,v);
	else
		return t[lchild].sum + query(rchild,mid + 1,r,v);
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> n;
	for(int i = 1;i <= n;i++){
		cin >> a[i];
		tmp[++top] = a[i];
	}
	//离散化 
	sort(tmp + 1,tmp + top + 1);
	top = unique(tmp + 1,tmp + top + 1) - (tmp + 1);
	for(int i = 1;i <= n;i++)
		a[i] = lower_bound(tmp + 1,tmp + top + 1,a[i]) - tmp;
	
	for(int i = 1;i <= n;i++){
		update(1,1,top,a[i],1);//将a[i]在计数器上加1（在权值线段树上更新） 
		ans += i - query(1,1,top,a[i]);//a[i]可以与在它前面且比a[i]大的数构成逆序对 ，即i减去[1,i]中不超过a[i]的数  
	}
	cout << ans;
	return 0;
}

例题 2：三元上升子序列

#include<bits/stdc++.h>
#define mid ((l + r) >> 1)
#define lchild (root << 1)
#define rchild ((root << 1) + 1)
using namespace std;
const int N = 3e4 + 9,M = 1e5 + 9;
int n;
int a[N],max_a/*值域*/;
struct node{
	int sum;
} t[M << 2];
bool in_range(int l,int r,int L,int R){
	return L <= l && r <= R;
}
bool out_range(int l,int r,int L,int R){
	return l > R || r < L;
}
void push_up(int root){
	t[root].sum = t[lchild].sum + t[rchild].sum;
}
void update(int root,int l,int r,int v,int k){
	if(l == r){
		t[root].sum += k;
		return;
	}
	if(v <= mid)
		update(lchild,l,mid,v,k);
	else
		update(rchild,mid + 1,r,v,k);
	push_up(root);
}
int query(int root,int l,int r,int L,int R){//查询值域在[L,R]范围内的数的总出现次数
	if(out_range(l,r,L,R))
		return 0;
	if(in_range(l,r,L,R))	
		return t[root].sum;
	return query(lchild,l,mid,L,R) + query(rchild,mid + 1,r,L,R);
}
//val1[i]：在a[i]前有多少个数小于a[i]
//val2[i]：在a[i]后有多少个数大于a[i]
int val1[N],val2[N];
long long ans;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> n;
	for(int i = 1;i <= n;i++){
		cin >> a[i];
		max_a = max(max_a,a[i]);
	}
	for(int i = 1;i <= n;i++){
		update(1,1,max_a,a[i],1);
		val1[i] = query(1,1,max_a,1,a[i] - 1);
	}
	
	//撤销在权值线段树上的修改
	for(int i = 1;i <= n;i++)
		update(1,1,max_a,a[i],-1);
	
	for(int i = n;i >= 1;i--){
		update(1,1,max_a,a[i],1);
		val2[i] = query(1,1,max_a,a[i] + 1,max_a);
	}
	
	for(int i = 1;i <= n;i++)
		ans += 1l * val1[i] * val2[i];
	cout << ans;
	return 0;
}

例题 3：楼兰图腾

本质就是对上一题进行了扩展。

题解（远古码风不喜勿喷）

例题 4：普通平衡树

没错，权值线段树也能维护部分平衡树维护的信息。

【3.2】动态开点线段树

在【0.3】中，已经提到了这个技巧。下面来看一道具体的题目。

例题 1：Physical Education Lessons

本题翻译得更直白一点就是给出一个 0/1 序列，支持将一个区间整体推平（整体修改为 \(0\) 或 \(1\)），求整个区间 \(1\) 的个数（区间和）。

比较卡常，需要使用快读。

#include<bits/stdc++.h>
const int N = 1e5 + 9,K = 15 * 1e6 + 9;
char gc(){
    static char buf[10000005],*t1 = buf,*t2 = buf;
    return t1 == t2 && (t2 = (t1 = buf) + fread(buf,1,1000000,stdin),t1 == t2) ? EOF : *t1++;
}
int read(){
    char c = gc();
    int x = 0;
    while(c < 48 || c > 57)
        c = gc();
    while(c >= 48 && c <= 57){
        x = (x << 3) + (x << 1) + c - 48;
        c = gc();
    }
    return x;
}
int n,q;
struct node{
    int val,tag,lchild,rchild;
} tree[K];
int cnt;
int len(int l,int r){
    return r - l + 1;
}
bool in_range(int l,int r,int now_l,int now_r){
    return l <= now_l && now_r <= r;
}
bool out_range(int l,int r,int now_l,int now_r){
    return now_r < l || now_l > r;
}
void make_tag(int root,int tag,int l,int r){
    tree[root].tag = tag;
    tree[root].val = tag * len(l,r);
}
void push_down(int root,int l,int r){
    if(tree[root].tag == -1)
        return;
    int mid = (l + r) >> 1;
    make_tag(tree[root].lchild,tree[root].tag,l,mid);
    make_tag(tree[root].rchild,tree[root].tag,mid + 1,r);
    tree[root].tag = -1;
}
void update(int root,int l,int r,int now_l,int now_r,int v){
    if(in_range(l,r,now_l,now_r)){
        make_tag(root,v,now_l,now_r);
        return;
    }
    int mid = (now_l + now_r) >> 1;
    if(!out_range(l,r,now_l,now_r)){
        if(!tree[root].lchild && !tree[root].rchild){
            tree[root].lchild = ++cnt;
            tree[root].rchild = ++cnt;
        }
        push_down(root,now_l,now_r);
        update(tree[root].lchild,l,r,now_l,mid,v);
        update(tree[root].rchild,l,r,mid + 1,now_r,v);
        tree[root].val = tree[tree[root].lchild].val + tree[tree[root].rchild].val;
    }
}
int main(){
    n = read();q = read();
    int root = ++cnt;
    tree[root].tag = 1;
    for(;q;q--){
        int l,r,op;
        l = read(),r = read(),op = read() - 1;
        update(root,l,r,1,n,op);
        printf("%d\n",tree[root].val);
    }
    return 0;
}

【3.3】李超线段树

更好的阅读体验

【3.3.0】李超线段树维护的问题

李超线段树主要是维护平面上的线段以及 $$

【3.3.1】问题的转化

众所周知，线段树是维护区间的，但是维护二维平面内的线段不能直接用区间维护，所以我们首先转换一下题意：

  • 加入一个一次函数，定义域为 \([l,r]\)；
  • 给定 \(k\)，求定义域包含 \(k\) 的所有一次函数中，在 \(x = k\) 处取值最大的那个，如果有多个函数取值相同，选编号最小的。

特别的，当一个线段不存在斜率时可以转换成斜率为 \(0\)，截距为 \(\max(y_0,y_1)\) 的直线（由题意这种情况交点取最顶部的顶点）。

本题的关键在于 \(k\) 为整数，因为 \(k\) 为整数，我们根本不需要保留整个线段，只需要保留线段中 \(x\) 为整数的点。

每个整数 \(x\) 可以看作序列中的下标，加入一个点相当于修改对应下标（\(x\) 坐标）的值

这样，我们就将其转化为一个区间修改，单点查询的问题。

【3.3.2】李超线段树的修改/查询

依照传统线段树的思路，我们还是通过分治和懒标记进行区间修改。

但是在一个区间内是没有最优线段的，只有在取一个特定的 \(x\) 时才有。所以，我们考虑每个节点维护包含对应区间所有直线在 横坐标 \(x\) 取一个一个特殊点时的最优线段。

不难想到这个特殊点为该区间的中点。

所以每个结点的懒标记维护的是横坐标 \(x\) 取该区间中点时的最优线段（但是这个懒标记无法保证任何时候都是在中点处最优的线段，原因讲到查询时会解释）。

在传统线段树中，区间修改（带懒标记应该是这样的）：

//[l,r]表示当前区间，[L,R]表示修改的区间
void update(int root,int l,int r,int L,int R,int id){
	if(out_range(l,r,L,R))//完全不在[L,R]内直接返回
		return;
	if(in_range(l,r,L,R)){//完全包含在[L,R]内更新懒标记
		make_tag(root,l,r,id);
		return;
	}
    //分别进入两子区间
	update(lchild,l,mid,L,R,id);
	update(rchild,mid + 1,r,L,R,id);
}

但是我们发现，在本题中，由懒标记的定义，当该线段的一部分（\([l,r]\)）完全包含在修改区间 \([L,R]\) 中时，不仅维护 \([l,r]\) 区间结点的懒标记会发生变化，其子节点也会发生变化，所以我们还得把懒标记下传。

对于该区间，如果在中点处取值当前修改线段与该结点维护的最优线段更优，直接拿当前线段替换，并把当前线段替换成在中点处不优的线段。

然后，我们分别比较两线段在左端点 \(l\) 的取值和在右端点 \(r\) 的取值：

如果中点处不优的线段在左端点处的取值更优，那么递归到左子节点下传。

如果中点处不优的线段在右端点处的取值更优，那么递归到右子节点下传。

如果都不优，那么该线段在该区间及子区间将来无论如何都不可能最优线段，可以停止下传。

int CMP(double x,double y){//比较两浮点数 
	if(x - y > eps)
		return 1;
	if(y - x > eps)
		return -1;
	return 0;
}
bool cmp(int id1,int id2,int x){//比较线段id1在x处是否优于id2 ，用于提升代码可读性和降低编码复杂度
	int comp = CMP(calc(id1,x),calc(id2,x));
	return comp == 1 || (!comp && id1 < id2);//id1比id2在x处更优，当且仅当id1在x处的取值更优或x取值相等但id1编号更小
}
void push_down(int root,int l,int r,int id){
	if(cmp(id,t[root].id,mid))//如果当前线段比结点维护的线段更优，替换掉
		swap(id,t[root].id);
        //将不是更优的线段下传（因为此时 id 中点处不优，所以以下最多只有1个if成立）
	if(cmp(id,t[root].id,l))
		push_down(lchild,l,mid,id);
	if(cmp(id,t[root].id,r))
		push_down(rchild,mid + 1,r,id);
}

因为 push_down 函数两个 if 最多只有一个成立，所以 push_down 函数的复杂度为 \(O(\log V)\)（\(V\) 为 \(x\) 最大值）。同样的，update函数复杂度也是 \(O(\log V)\)（覆盖区间个数为 \(O(\log V)\)），每个覆盖区间又要一次 \(O(\log V)\) 的 push_down，所以修改部分的总复杂度为 \(O(\log^2 V)\)。

我们看到，查询部分显然是个单点查询问题，但真的只需要访问代表查询点的那个叶节点吗？

不是的。

上文提到，懒标记无法保证任何时候都是在中点处最优的线段，很容易构造出（去除强制在线的影响）：

1 7 2 9 2
1 2 2 10 10

我们令整个区间长度为 \(10\)。

在本例中，加入第 \(1\) 条使其在 \(x = 8\) 处最优。但是第二条线段在 \(x = 8\) 处显然更优，但由于第 \(1\) 条线段与与整个区间的中点无交，所以第 \(2\) 条线段不会继续下传，因此维护 \([6,10]\) 区间节点（中点为 \(8\)）维护的“最优”还是线段 \(1\)。

所以，我们需要将所有包含 \(x = k\) 的区间对应的结点全部扫一遍，取所有结点懒标记的最优者。

在这里维护了一个 better 函数，因此这里的 query 返回值不需要用 pair。

int better(int id1,int id2,int x){//返回id1,id2在x处较优者 
	return cmp(id1,id2,x) ? id1 : id2;
}
int query(int root,int l,int r,int k){
	if(out_range(k,k,l,r))
		return 0;
	if(l == r)//递归边界
		return t[root].id;
	return better(t[root].id,better(query(lchild,l,mid,k),query(rchild,mid + 1,r,k),k),k);
}

复杂度为 \(O(\log V)\)。

【3.3.3】完整代码

#include<iostream>
#define lchild (root << 1)
#define rchild ((root << 1) + 1)
#define mid ((l + r) >> 1)
using namespace std;
const int N = 1e5 + 9,MAXX = 39989,MAXY = 1e9;
const double eps = 1e-9;
struct line{//存线段的结构体
	double k,b;
} a[N];
int cnt;
void add_line(int x0,int y0,int x1,int y1){//加入一线段
	cnt++;
	if(x0 == x1){
		a[cnt].k = 0;
		a[cnt].b = max(y0,y1);
		return;
	}
	a[cnt].k = (double)(y1 - y0) / (double)(x1 - x0);
	a[cnt].b = (double)y0 - (double)(x0 * a[cnt].k);
}
double calc(int id,double x){//计算第i条直线在x处的值。 
	return a[id].k * x + a[id].b;
}
//1:x > y
//-1:x < y
//0:x = y
int CMP(double x,double y){//比较两浮点数 
	if(x - y > eps)
		return 1;
	if(y - x > eps)
		return -1;
	return 0;
}
bool cmp(int id1,int id2,int x){//比较线段id1在x处是否优于id2 ，用于提升代码可读性和降低编码复杂度
	int comp = CMP(calc(id1,x),calc(id2,x));
	return comp == 1 || (!comp && id1 < id2);
}
int better(int id1,int id2,int x){//返回id1,id2在x处较优者 
	return cmp(id1,id2,x) ? id1 : id2;
}
bool in_range(int l,int r,int L,int R){
	return L <= l && r <= R;
}
bool out_range(int l,int r,int L,int R){
	return l > R || r < L;
}
struct node{
	int id;//该节点维护区间最优线段编号 
} t[MAXX << 2];
void push_down(int root,int l,int r,int id){
	if(cmp(id,t[root].id,mid))//如果当前线段比结点维护的线段更优，替换掉
		swap(id,t[root].id);
        //将不是更优的线段下传（因为此时 id 中点处不优，所以以下最多只有1个if成立）
	if(cmp(id,t[root].id,l))
		push_down(lchild,l,mid,id);
	if(cmp(id,t[root].id,r))
		push_down(rchild,mid + 1,r,id);
}
void update(int root,int l,int r,int L,int R,int id){
	if(out_range(l,r,L,R))
		return;
	if(in_range(l,r,L,R)){
		push_down(root,l,r,id);
		return;
	}
	update(lchild,l,mid,L,R,id);
	update(rchild,mid + 1,r,L,R,id);
}
int query(int root,int l,int r,int k){
	if(out_range(k,k,l,r))
		return 0;
	if(l == r)
		return t[root].id;
	return better(t[root].id,better(query(lchild,l,mid,k),query(rchild,mid + 1,r,k),k),k);
}
int n,ans;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> n;
	for(int i = 1;i <= n;i++){
		int op;
		cin >> op;
		if(op == 0){
			int k;
			cin >> k;
			k = (k + ans - 1) % MAXX + 1;
			ans = query(1,1,MAXX,k);
			cout << ans << '\n';
		}
		if(op == 1){
			int x0,y0,x1,y1;
			cin >> x0 >> y0 >> x1 >> y1;
			x0 = (x0 + ans - 1) % MAXX + 1;
			x1 = (x1 + ans - 1) % MAXX + 1;
			y0 = (y0 + ans - 1) % MAXY + 1;
			y1 = (y1 + ans - 1) % MAXY + 1;
			if(x0 > x1){
				swap(x0,x1);
				swap(y0,y1);
			}
			add_line(x0,y0,x1,y1);
			update(1,1,MAXX,x0,x1,cnt);
		}
	}
	return 0;
}

例题 1：Blue Mary 开公司

这题比板题还直接，连转换都不需要，直接维护的是一次函数（也不存在两端点了）。

#include<iostream>
#define lchild (root << 1)
#define rchild ((root << 1) + 1)
#define mid ((l + r) >> 1)
using namespace std;
const int N = 1e5 + 9,MAXX = 5e4 + 1,MAXY = 1e9;
const double eps = 1e-9;
struct line{//存线段的结构体
	double k,b;
} a[N];
int cnt;
void add_line(int x0,double y0,int x1,double y1){//加入一线段
	cnt++;
	a[cnt].k = (y1 - y0) / (double)(x1 - x0);
	a[cnt].b = y0 - (double)(x0 * a[cnt].k);
}
double calc(int id,double x){//计算第i条直线在x处的值。 
	return a[id].k * x + a[id].b;
}
//1:x > y
//-1:x < y
//0:x = y
int CMP(double x,double y){//比较两浮点数
	if(x - y > eps)
		return 1;
	if(y - x > eps)
		return -1;
	return 0;
}
bool cmp(int id1,int id2,int x){//比较线段id1在x处是否优于id2 ，用于提升代码可读性和降低编码复杂度
	int comp = CMP(calc(id1,x),calc(id2,x));
	return comp == 1 || (!comp && id1 < id2);
}
int better(int id1,int id2,int x){//返回id1,id2在x处较优者
	return cmp(id1,id2,x) ? id1 : id2;
}
bool in_range(int l,int r,int L,int R){
	return L <= l && r <= R;
}
bool out_range(int l,int r,int L,int R){
	return l > R || r < L;
}
struct node{
	int id;//该节点维护区间最优线段编号 
} t[MAXX << 2];
void push_down(int root,int l,int r,int id){
	if(cmp(id,t[root].id,mid))//如果当前线段比结点维护的线段更优，替换掉
		swap(id,t[root].id);
        //将不是更优的线段下传（因为此时 id 中点处不优，所以以下最多只有1个if成立）
	if(cmp(id,t[root].id,l))
		push_down(lchild,l,mid,id);
	if(cmp(id,t[root].id,r))
		push_down(rchild,mid + 1,r,id);
}
void update(int root,int l,int r,int L,int R,int id){
	if(out_range(l,r,L,R))
		return;
	if(in_range(l,r,L,R)){
		push_down(root,l,r,id);
		return;
	}
	update(lchild,l,mid,L,R,id);
	update(rchild,mid + 1,r,L,R,id);
}
int query(int root,int l,int r,int k){
	if(out_range(k,k,l,r))
		return 0;
	if(l == r)
		return t[root].id;
	return better(t[root].id,better(query(lchild,l,mid,k),query(rchild,mid + 1,r,k),k),k);
}
int n,ans;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> n;
	for(int i = 1;i <= n;i++){
		string op;
		cin >> op;
		if(op == "Query"){
			int k;
			cin >> k;
			int id = query(1,1,MAXX,k);
			ans = a[id].k * k + a[id].b;
			cout << (int)(ans) / 100 << '\n';
		}
		else{
			int x0 = 1,x1 = MAXX - 1;
			double s,p;
			cin >> s >> p;
			add_line(x0,s,x1,s + (x1 - x0) * p);
			update(1,1,MAXX,x0,x1,cnt);
		}
	}
	return 0;
}

【3.4】区间最值操作/区间历史最值

未完待续（逃）

【4】线段树的合并与分裂

注：这里所说的线段树合并/分裂是指动态开点权值线段树的合并与分裂。

【4.0】线段树的合并与分裂的定义

线段树合并可以看作是求将两个可重集合合并之后对应的权值线段树。

而线段树分裂是将一个可重集前 \(k\) 小的数与之后的数分成两个集合，对应的权值线段树就要裂成两棵权值线段树。

可以看出，线段树的合并与分裂不是互为逆操作的。

【4.1】线段树合并

线段树合并一般是针对上文提到的动态开点权值线段树。

为了省空间，我们不会建一棵新树来存储合并的结果，必须是将结果保存在其中一棵树上。

【4.1.1】线段树合并的前提条件

线段树合并要求两棵线段树线段树“形态一致”（这里的形态一致是指扩充为完整的线段树时形态一致），换句话说，就是两棵权值线段树维护的值域一致。

这样，我们就可以用“同一位置”来描述两棵线段树维护相同值域信息的节点了。

相同位置的节点总共有 \(2\) 种情况：

  1. 两棵树都有这个节点。

  2. 两棵树有一棵树没有这个节点。

未完待续（逃）

【4.1.2】核心代码

以下代码实现了将以 root1 和 root2 为根的两棵子树合并，然后返回合并后的树根

int merge(int root,int root2,int l,int r){
	if(!root || !root2)
		return root | root2;
	if(l == r){
		t[root].val += t[root2].val;
		return root;
	}
	lchild = merge(lchild,lchild2,l,mid);
	rchild = merge(rchild,rchild2,mid + 1,r);
	push_up(root);
	return root;
}

例题 1：线段树合并

线段树合并板子，再结合一点树上差分的知识即可。

关于我在树剖上翻车了这件事 \(\dots\)

#include<bits/stdc++.h>
#define mid ((l + r) >> 1)
#define lchild t[root].Lchild
#define rchild t[root].Rchild
#define lchild2 t[root2].Lchild
#define rchild2 t[root2].Rchild
using namespace std;
const int N = 1e5 + 9;
int n,m;
struct edge{
	int to,nex;
} e[N << 1];
int head[N],ecnt;
void addedge(int u,int v){
	ecnt++;
	e[ecnt] = (edge){v,head[u]};
	head[u] = ecnt;
}

int dep[N],w_ch[N],siz[N];//深度、重儿子、子树大小 
int fa[N];//父亲 
void dfs1(int u,int father){
	siz[u] = 1;
	fa[u] = father;
	dep[u] = dep[fa[u]] + 1;
	for(int i = head[u];i;i = e[i].nex){
		int v = e[i].to;
		if(v == fa[u])
			continue;
		dfs1(v,u);
		siz[u] += siz[v];
		if(siz[v] > siz[w_ch[u]])
			w_ch[u] = v;
	}
}
int w_top[N];//重链链头 
void dfs2(int u,int top){
	w_top[u] = top;
	if(w_ch[u]){
		dfs2(w_ch[u],top);
		for(int i = head[u];i;i = e[i].nex){
			int v = e[i].to;
			if(v == fa[u] || v == w_ch[u])
				continue;
			dfs2(v,v);
		}
	}
}

struct OPTION{
	int u,v,type;
} op[N];
int max_v;

int LCA(int u,int v){
	while(w_top[u] != w_top[v]){
		if(dep[w_top[u]] < dep[w_top[v]])
			swap(u,v);
		u = fa[w_top[u]];
	}
	return (dep[u] < dep[v]) ? u : v;
}

struct node{
	int Max,id;
	int Lchild,Rchild;
} t[N << 8];
int Root[N],node_cnt;
void push_up(int root){
	if(t[lchild].Max > t[rchild].Max || (t[lchild].Max == t[rchild].Max && t[lchild].id < t[rchild].id)){
		t[root].Max = t[lchild].Max;
		t[root].id = t[lchild].id;
	}
	else{
		t[root].Max = t[rchild].Max;
		t[root].id = t[rchild].id;
	}
}
void update(int root,int l,int r,int v,int k){
	if(l == r){
		t[root].Max += k;
		t[root].id = l;
		return;
	}
	if(v <= mid){
		if(!lchild)
			lchild = ++node_cnt;
		update(lchild,l,mid,v,k);
	}
	else{
		if(!rchild)
			rchild = ++node_cnt;
		update(rchild,mid + 1,r,v,k);
	}
	push_up(root);
}
int merge(int root,int root2,int l,int r){
	if(!root || !root2)
		return root | root2;
	if(l == r){
		t[root].Max += t[root2].Max;
		t[root].id = l;
		return root;
	}
	lchild = merge(lchild,lchild2,l,mid);
	rchild = merge(rchild,rchild2,mid + 1,r);
	push_up(root);
	return root;
}
void dfs3(int u){
	for(int i = head[u];i;i = e[i].nex){
		int v = e[i].to;
		if(v == fa[u])
			continue;
		dfs3(v);
		merge(Root[u],Root[v],1,max_v);
	}
}


int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> n >> m;
	for(int i = 1;i <= n;i++)
		Root[i] = ++node_cnt; 
	for(int i = 1;i < n;i++){
		int u,v;
		cin >> u >> v;
		addedge(u,v);
		addedge(v,u);
	}
	dfs1(1,0);
	dfs2(1,0);
	for(int i = 1;i <= m;i++){
		cin >> op[i].u >> op[i].v >> op[i].type;
		max_v = max(max_v,op[i].type);
	}
	max_v++;
	for(int i = 1;i <= m;i++){
		int u = op[i].u,v = op[i].v,type = op[i].type;
		int lca = LCA(u,v);
		update(Root[u],1,max_v,type,1);
		update(Root[v],1,max_v,type,1);
		update(Root[lca],1,max_v,type,-1);
		if(fa[lca])
			update(Root[fa[lca]],1,max_v,type,-1);
	}
	dfs3(1);
	for(int i = 1;i <= n;i++)
		cout << t[Root[i]].id << '\n';
	return 0;
}

【4.2】线段树分裂

未完待续（逃）

热门相关：冒牌老婆很神秘   逃妻鲜嫩嫩：霸道老公，吻够没   神级幸运星   奉旨成婚：悍妃训夜王   帝王娇宠：小萌妃，乖一点