线段树

Thu Oct 03 2024

zzcoe

30 分钟

数据结构与算法数据结构线段树

3964 字

线段树模板#

【AgOHの数据结构】线段树分裂合并_哔哩哔哩_bilibili线段树是一种可以维护满足结合律的区间信息的数据结构 Pasted image 20240225004219

P3372 【模板】线段树 1 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)P3374 【模板】树状数组 1 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

CPP

#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define N 100005
#define LL long long
#define lc u<<1
#define rc u<<1|1
LL w[N];
struct Tree{ //线段树
    LL l,r,sum,add;
}tr[N*4];

void pushup(LL u){ //上传
    tr[u].sum=tr[lc].sum+tr[rc].sum;
}
void pushdown(LL u){ //下传
    if(tr[u].add){//lazy标识不为零
        //下放给两个儿子
        tr[lc].sum+=tr[u].add*(tr[lc].r-tr[lc].l+1),
        tr[rc].sum+=tr[u].add*(tr[rc].r-tr[rc].l+1),
        tr[lc].add+=tr[u].add,
        tr[rc].add+=tr[u].add,
        //lazy表示置零
        tr[u].add=0;
    }
}
void build(LL u,LL l,LL r){ //建树，信息都在叶子结点上
    tr[u]={l,r,w[l],0};
    if(l==r) return;
    LL m=l+r>>1;
    build(lc,l,m);
    build(rc,m+1,r);
    pushup(u);
}
void updata(int u, int x, int k){//点修改
    if (tr[u].l == x && tr[u].r == x){//叶子结点修改
        tr[u].sum+=k;
        return ;
    }
    int m= tr[u].l + tr[u].r >> 1;//非叶子结点则裂开
    if (x<=m) updata(lc,x,k);
    if (x>m) updata(rc,x,k);
    tr[u].sum= tr[lc].sum + tr[rc].sum;
}

void change(LL u,LL l,LL r,LL k){ //区修
    if(l<=tr[u].l&&tr[u].r<=r){
        tr[u].sum+=(tr[u].r-tr[u].l+1)*k;
        tr[u].add+=k;
        return;
    }
    LL m=tr[u].l+tr[u].r>>1;
    pushdown(u);
    if(l<=m) change(lc,l,r,k);
    if(r>m) change(rc,l,r,k);
    pushup(u);
}
LL query(LL u,LL l,LL r){ //区查
    if(l<=tr[u].l && tr[u].r<=r) return tr[u].sum;
    LL m=tr[u].l+tr[u].r>>1;
    pushdown(u);
    LL sum=0;
    if(l<=m) sum+=query(lc,l,r);
    if(r>m) sum+=query(rc,l,r);
    return sum;
}
int main(){
    int n,m,op,x,y,k;
    cin>>n>>m;
    for(int i=1; i<=n; i ++) cin>>w[i];

    build(1,1,n);
    while(m--){
        cin>>op>>x>>y;
        if(op==2)cout<<query(1,x,y)<<endl;
        else cin>>k,change(1,x,y,k);
    }
    return 0;
}

例题一#

Queue - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)题目大意：给定 n 个正整数 $a_1…_n$ 。需要输出一个 n 个数，设此时正在处理第 i 个数： - 设 $a_j < a_i,j > i$ 。 - 在满足第一条的基础上使 j-i-1 尽可能大，此时 j - i - 1 即为答案。 $2 \leq n \leq 10^5，a_i \leq 10^9$ , 如果对于某个 i，不存在任何一个 j 满足 $a_j < a_i$ 且 $j > i$ ，则输出 -1。

即找最远小于 a[i] 的值的位置

CPP

#include<iostream>
#include <queue>
#include <cstring>
#define ll long long
#define lc u<<1
#define rc u<<1|1
using namespace std;
const ll maxn=1e5+5;
ll w[maxn];
struct tree{
	ll l,r,minsum,add;
}tr[maxn*4];

void updata(ll u){//向上修改维护线段树
	tr[u].minsum=min(tr[lc].minsum,tr[rc].minsum);
} 
void build(ll u,ll l,ll r){//建树
	tr[u]={l,r,w[l],0};
	if (l==r){
		return ;
	} 
	ll m=l+r>>1;
	build(lc,l,m);
	build(rc,m+1,r);
	updata(u);
}
ll diancha(ll u,ll k){//点查
	ll t=-1;
	if (tr[u].l==tr[u].r){
		if (tr[u].minsum<k){
			return tr[u].l;
		}
		return -1;
	}

	if (tr[u].minsum<k){
		if(tr[rc].minsum<k){//因为要找小于k的最远值，所以先考虑右边的
		//右边的最小值小于k则不必再考虑左边的
			t=max(t,diancha(rc,k));
		} else if (tr[lc].minsum<k){
			t=max(t,diancha(lc,k));
		}
	}
	
	return t;
}
int main (){
	int n;
	cin>>n;
	for (int i=1;i<=n;i++)
	{
		cin>>w[i];
	}
	build (1,1,n);
	
	for (int i=1;i<=n;i++)
	{
		ll t = diancha(1,w[i]);
		if (t<=i){
			cout<<"-1 ";
		}else {
			cout<<t-i-1<<" ";
		}
		
	}
	return 0;
}

例题四#

P3373 【模板】线段树 2 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)一个线段树上同时进行两种操作区间乘以及区间加代码：

CPP

#include <bits/stdc++.h>

#define MAXN 100010
#define ll long long

using namespace std;

int n, m, mod;
int a[MAXN];

struct Segment_Tree {
	ll sum, add, mul;
	int l, r;
}s[MAXN * 4];

void update(int pos) {
	s[pos].sum = (s[pos << 1].sum + s[pos << 1 | 1].sum) % mod;
    return;
}

void pushdown(int pos) { //pushdown的维护
	S[pos << 1]. Sum = (s[pos << 1]. Sum * s[pos]. Mul + s[pos]. Add * (s[pos << 1]. R - s[pos << 1]. L + 1)) % mod;
	S[pos << 1 | 1]. Sum = (s[pos << 1 | 1]. Sum * s[pos]. Mul + s[pos]. Add * (s[pos << 1 | 1]. R - s[pos << 1 | 1]. L + 1)) % mod;
	
	S[pos << 1]. Mul = (s[pos << 1]. Mul * s[pos]. Mul) % mod;
	S[pos << 1 | 1]. Mul = (s[pos << 1 | 1]. Mul * s[pos]. Mul) % mod;
	
	S[pos << 1]. Add = (s[pos << 1]. Add * s[pos]. Mul + s[pos]. Add) % mod;
	S[pos << 1 | 1]. Add = (s[pos << 1 | 1]. Add * s[pos]. Mul + s[pos]. Add) % mod;
		
	S[pos]. Add = 0;
	S[pos]. Mul = 1;
	Return; 
}

Void build_tree (int pos, int l, int r) { //建树
	S[pos]. L = l;
	S[pos]. R = r;
	S[pos]. Mul = 1;
	
	If (l == r) {
		S[pos]. Sum = a[l] % mod;
		Return;
	}
	
	Int mid = (l + r) >> 1;
	Build_tree (pos << 1, l, mid);
	Build_tree (pos << 1 | 1, mid + 1, r);
	Update (pos);
	Return;
}

Void ChangeMul (int pos, int x, int y, int k, int t) { 
	If (x <= s[pos]. L && s[pos]. R <= y) {
		If (t==2){
			S[pos]. Add = (s[pos]. Add + k) % mod;
			S[pos]. Sum = (s[pos]. Sum + k * (s[pos]. R - s[pos]. L + 1)) % mod;
		}else if (t==1){
			S[pos]. Add = (s[pos]. Add * k) % mod;
			S[pos]. Mul = (s[pos]. Mul * k) % mod;
			S[pos]. Sum = (s[pos]. Sum * k) % mod;
		}
		
		Return;
	}
	
	Pushdown (pos);
	Int mid = (s[pos]. L + s[pos]. R) >> 1;
	If (x <= mid) ChangeMul (pos << 1, x, y, k, t);
	If (y > mid) ChangeMul (pos << 1 | 1, x, y, k, t);
	Update (pos);
	Return;
}

Ll AskRange (int pos, int x, int y) { //区间询问
	If (x <= s[pos]. L && s[pos]. R <= y) {
		Return s[pos]. Sum;
	}
	
	Pushdown (pos);
	Ll val = 0;
	Int mid = (s[pos]. L + s[pos]. R) >> 1;
	If (x <= mid) val = (val + AskRange (pos << 1, x, y)) % mod;
	If (y > mid) val = (val + AskRange (pos << 1 | 1, x, y)) % mod;
	Return val;
}

Int main () {
	Scanf ("%d%d", &n, &mod);
	
	For (int i = 1; i <= n; i++) {
		Scanf ("%d", &a[i]);
	}
	
	Build_tree (1, 1, n);
	Cin>>m;
	For (int i = 1; i <= m; i++) {
		Int opt, x, y;
		Scanf ("%d%d%d", &opt, &x, &y);
		If (opt == 3) {
			Printf ("%lld\n", AskRange (1, x, y));
		}else {
			Int k;
			Scanf ("%d", &k);
			ChangeMul (1, x, y, k, opt);
		}
	}
    
	Return 0;
}

例题三#

P 3740 [HAOI 2014] 贴海报 - 洛谷 | 计算机科学教育新生态 (luogu. Com. Cn)不需要建树的线段树，每一步大操作都是一次性的，且树上只存储少量的信息，在不建树的情况下可以节省很多空间复杂度

解题思路：线段树维护区间是否被染色：区间修改没被染色的点，标记，++ans；如果区间的点全被染过色，那ans不变。注意数据的处理顺序与输入顺序相反。因为最后输入的在最上面，一定可以ans++，所以先处理，之后处理先输入的数据，如果它需要的区间已经被标记则表示它被后输入的覆盖了，于是不能ans++，直接return。可以结合代码在仔细理解

代码：

CPP

#include <iostream>
#include <algorithm>
#include <cstring>
#include <set>
#define ll long long
#define lc u<<1
#define rc u<<1|1 
Using namespace std;
Const int maxn=1 e 7+5;
Bool vis[maxn<<2];
Bool flag;
Int read ()
{
    Int now=0; char c=getchar ();
    while (c<'0'||c>'9') c=getchar ();
    While (c>='0'&&c<='9') now=(now<<3)+(now<<1)+c-'0', c=getchar ();
    Return now;
}
Void updata (int u){
	Vis[u]=vis[lc]&&vis[rc];
}
Void Modify (int u, int l, int r, int L, int R){
	If (vis[u]){
		Return ;
	}
	if (L<=l&&R>=r){
		Flag=true;
		Vis[u]=true;
		Return ;
	}
	Int m=(l+r)>>1;
	If (L<=m){
		Modify (lc, l, m, L, R);
	}
	If (R>m){
		Modify (rc, m+1, r, L, R);
	}
	Updata (u);
	Return ;
} 
Int main ()
{
	Int n, m;
	Cin>>n>>m;
	Int a[1005], b[1005];
	For (int i=m; i>=1; i--){
		Cin>>a[i]>>b[i];
	}
	Int ans=0;
	For (int i=1; i<=m; i++){
		Flag=false;
		Modify (1,1, n, a[i], b[i]);
		If (flag){
			Ans++;
		}
	}
	Cout<<ans<<endl;
	Return 0;
}

线段树分裂合并#

P 4556 [Vani 有约会]雨天的尾巴 /【模板】线段树合并_哔哩哔哩_bilibili

例题#

P5494 【模板】线段树分裂 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题意描述：给出一个可重集 𝑎（编号为 1），它支持以下操作：

0 p x y：将可重集 𝑝 中大于等于 𝑥且小于等于 𝑦 的值移动到一个新的可重集中（新可重集编号为从 2 开始的正整数，是上一次产生的新可重集的编号+1）。

1 p t：将可重集 𝑡t 中的数放入可重集 𝑝，且清空可重集 𝑡（数据保证在此后的操作中不会出现可重集 𝑡）。

2 p x q：在 𝑝这个可重集中加入 𝑥 个数字 𝑞。//也就是 r=l=q，val+=x；

3 p x y：查询可重集 𝑝 中大于等于 𝑥x 且小于等于 𝑦 的值的个数。

4 p k：查询在 𝑝 这个可重集中第 𝑘 小的数，不存在时输出 -1。

输入格式

第一行两个整数 𝑛,𝑚n, m，表示可重集中的数在 1∼𝑛1∼n 的范围内，有 𝑚m 个操作。

接下来一行 𝑛n 个整数，表示 1∼𝑛1∼n 这些数在 𝑎a 中出现的次数 (𝑎𝑖≤𝑚)(ai≤m)。

接下来的 𝑚m 行每行若干个整数，第一个数为操作的编号 𝑜𝑝𝑡opt（0≤𝑜𝑝𝑡≤40≤opt≤4），以题目描述为准。

输出格式

依次输出每个查询操作的答案。

CPP

#include <iostream>
#include <cstdio>
#include <ctime>
Using namespace std;
//==========================================
Const int maxn = 2 e 5 + 5;
Typedef long long ll;
Struct Node
{
    Int l, r;//表示左右区间
    Ll val;//表示元素个数
}sgt[maxn*40];      //? 40 = 2*maxm*log 2 (maxn)，相当于一个超大的线段树，可拆分
Int cnt, root[maxn];//指向线段树的根，表示为一个新的线段树

Inline void pushup (int k) { sgt[k]. Val = sgt[sgt[k]. L]. Val + sgt[sgt[k]. R]. Val; }
Void modify (int l, int r, int &k, int p, int x)     // 单点修改: p 位置的值加上 x，空间复杂度 O (logn)
{
    If (! K) k=++cnt;     // 如果到了 NIL 结点就新建一个
    Sgt[k]. Val += x;    // 单点修改的加法直接一条线上全部加上 x 即可
    If (l==r) return;
    Int m = (l+r)>>1;
    If (p<=m) modify (l, m, sgt[k]. L, p, x);      // 在左子树
    Else modify (m+1, r, sgt[k]. R, p, x);        // 在右子树
}
Void merge (int &x, int y)        // 把 y 结点的内容合并到 x 结点上，此写法不消耗空间
{
    If (! (x&&y)) x|=y;           // 如果二者有 NULL 结点
    Else 
    {
        Sgt[x]. Val += sgt[y]. Val;   // 维护加法，直接加就是了
        Merge (sgt[x]. L, sgt[y]. L);  // 递归合并两结点的左子树
        Merge (sgt[x]. R, sgt[y]. R);  // 递归合并两结点的右子树
    }
}
Int split (int l, int r, int &k, int x, int y)   // 从 k 中分离出[x, y]区间并返回新结点编号，空间复杂度 O (2 logn)
{
    Int n = ++cnt;
    if (x<=l&&y>=r)      // 如果 k 结点维护的区间在[x, y]中
    {
        Sgt[n] = sgt[k];    // 直接拿过来便是
        K = 0;              // 置为 NULL，断掉联系
    }
    Else 
    {
        Int m = (l+r)>>1;
        If (x<=m) sgt[n]. L = split (l, m, sgt[k]. L, x, y);        // 若左子树中有区间信息
        If (y>m)  sgt[n]. R = split (m+1, r, sgt[k]. R, x, y);      // 若右子树中有区间信息
        Pushup (k);
        Pushup (n);      // 更改后记得更新值
    }
    Return n;
}
Ll query (int l, int r, int k, int x, int y)     // 区间查询
{
    if (x<=l&&y>=r) return sgt[k]. Val;
    Int m = (l+r)>>1;
    Ll sum = 0;
    If (x<=m) sum += query (l, m, sgt[k]. L, x, y);
    If (y>m)  sum += query (m+1, r, sgt[k]. R, x, y);
    Return sum;
}
Ll query (int l, int r, int k, int kth)         // 单点查询
{
    If (l==r) return l;
    Int m = (l+r)>>1;
    If (kth<=sgt[sgt[k]. L]. Val) return query (l, m, sgt[k]. L, kth);
    Else return query (m+1, r, sgt[k]. R, kth-sgt[sgt[k]. L]. Val);
}
Signed main (signed argc, char const *argv[])
{
    Clock_t c 1 = clock ();
#ifdef LOCAL
    Freopen ("in. In", "r", stdin);
    Freopen ("out. Out", "w", stdout);
#endif
    //======================================
    Int n, m;
    Cin>>n>>m;
    For (int i=1; i<=n; i++)
    {
        Int x;
        Cin>>x;
        Modify (1, n, root[1], i, x);            // 初始状态下值都为 0，所以加 x 即为置为 x
    }
    Int last = 1;
    While (m--)
    {
        Int opt, x, y, z;
        Cin>>opt>>x>>y;
        Switch (opt)
        {
        Case 0:
            Cin>>z;
            Root[++last] = split (1, n, root[x], y, z);
            Break;
        Case 1:
            Merge (root[x], root[y]);
            Break;
        Case 2:
            Cin>>z;
            Modify (1, n, root[x], z, y);
            Break;
        Case 3:
            Cin>>z;
            Cout<<query (1, n, root[x], y, z)<<endl;
            Break;
        Case 4:
            If (y>sgt[root[x]]. Val) cout<<-1<<endl;      // 若只有 4 个元素却来查询第 5 大元素（例如），那么结果即为-1
            Else cout<<query (1, n, root[x], y)<<endl;
            Break;
        }
    }
    //======================================
End:
    Cerr << "Time Used: " << clock () - c 1 << "ms" << endl;
    Return 0;
}

动态开点线段树#

C48 线段树+动态开点 CF915E Physical Education Lessons_哔哩哔哩_bilibili

Pasted image 20240503205623|1224 Pasted image 20240504172239

模板题#

Physical Education Lessons - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

时间超时，但逻辑正确可参考学习

CPP

#include <iostream>
#define ll long long
#define lc tr[u]. L
#define rc tr[u]. R
Using namespace std;
Const int MAXN=3 e 5+5;
Int tot=1;
Struct node {
    Int l, r, num, tag;
}tr[MAXN*50];
Void pushup (int u){
    Tr[u]. Num=tr[lc]. Num+tr[rc]. Num;
}
Void pushdown (int u, int l, int r){
    If (tr[u]. Tag==0){
        Return ;
    }
    Int m=(l+r)>>1;
    //开点
    If (! Tr[u]. L) tr[u]. L=++tot;
    If (! Tr[u]. R) tr[u]. R=++tot;
    If (tr[u]. Tag==1)//非工作日
    {
        Tr[lc]. Num=m-l+1;
        Tr[rc]. Num=r-m;
    }else if (tr[u]. Tag==2){//工作日
        Tr[lc]. Num=tr[rc]. Num=0;
    }
    Tr[lc]. Tag=tr[rc]. Tag=tr[u]. Tag;
    Tr[u]. Tag=0;
}
Void change (int &u, int l, int r, int x, int y, int tag){//u 必须为引用
	//开点
    If (! U){//因为此处会对 u 修改
        U=++tot;//如果不是引用，则 u 的左右子树永远指向 0
    }
    if (x<=l&&y>=r){
        If (tag==1){
            Tr[u]. Num=r-l+1;
        }else {
            Tr[u]. Num=0;
        }
        Tr[u]. Tag=tag;
        Return ;
    }
    Pushdown (u, l, r);
    Int m=(l+r)>>1;
    If (x<=m){
        Change (lc, l, m, x, y, tag);
    }
    If (y>m){
        Change (rc, m+1, r, x, y, tag);
    }
    Pushup (u);

}
Int main ()
{
    Int n, m, root=1;
    Cin>>n>>m;
    Int opt, l, r;
    For (int i=1; i<=m; i++){
        Cin>>l>>r>>opt;
        Change (root, 1, n, l, r, opt);
        Cout<<n-tr[root]. Num<<endl;
    }
    Return 0;
}

题二：#

T125847 【模板】动态开点线段树 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题三：#

P 3960 [NOIP 2017 提高组] 列队 - 洛谷 | 计算机科学教育新生态 (luogu. Com. Cn)

可持久化线段树（主席树）#

C49【模板】可持久化线段树（主席树）P3919 可持久化数组_哔哩哔哩_bilibili

理论#

Pasted image 20240504172813

实现#

建树#

Pasted image 20240504173258

点修#

Pasted image 20240504174024

点查#

Pasted image 20240504174145

代码实现#

例题：#

P3919 【模板】可持久化线段树 1（可持久化数组） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

CPP

#include <iostream>
#define ll long long
Using namespace std;
Const int MAXN=1 e 6+5;
Int root[MAXN], tot;
Int a[MAXN];
Struct node {
    Int l, r, num;
}tr[MAXN*25];
Void build (int &u, int l ,int r){//建树
    U=++tot;
    If (l==r){
        Tr[u]. Num=a[l];
        Return ;
    }
    Int m=(l+r)>>1;
    Build (tr[u]. L, l, m);
    Build (tr[u]. R, m+1, r);
}
Void change (int &u, int v, int l, int r, int p, int num){//点修
    U=++tot;
    Tr[u]=tr[v];
    If (l==r){
        Tr[u]. Num=num;
        Return ;
    }
    Int m=(l+r)>>1;
    If (p<=m){
        Change (tr[u]. L, tr[v]. L, l, m, p, num);
    }else {
        Change (tr[u]. R, tr[v]. R, m+1, r, p, num);
    }
    Return ;
}
Int query (int u, int l, int r, int p){//点查
   If (l==r){
       Return tr[u]. Num;
   }
   Int m=(l+r)>>1;
   If (p<=m){
      Return  query (tr[u]. L, l, m, p);
   }else {
      Return  query (tr[u]. R, m+1, r, p);
   }
}
Int main ()
{
    Int n, m;
    Cin>>n>>m;
    For (int i=1; i<=n; i++){
        Scanf ("%d",&a[i]);
//        cin>>a[i];
    }
    Build (root[0], 1, n);

    For (int i=1; i<=m; i++){
        Int u, opt, x, num;
        Scanf ("%d %d %d",&u,&opt,&x);
//        cin>>u>>opt>>x;
        If (opt==1){
            Scanf ("%d",&num);
//            cin>>num;
            Change (root[i], root[u], 1, n, x, num);
        }else {
            Root[i]=root [u];
            Cout<<query (root[u], 1, n, x)<<endl;
        }
    }
    Return 0;
}

线段树标记永久化#

标记永久化：就是修改时留下的懒标记并不下穿，也不删除，而是留在打上标记的那一个节点上。当查询经过这个节点时，就加上这个节点的懒标记造成的影响。

因此：标记永久化不需要 pushdown 以及 pushup 操作，可以避免一些不必要的计算，来节省时间

Pasted image 20240504220148

CPP

#include <iostream>
#define ll long long
Using namespace std;
Const int MAXN=1 e 6+5;
Int root[MAXN], tot;
Int a[MAXN];
Struct node {
    Int l, r, num, tag;//区间和，永久标记
}tr[MAXN*25];
Void build (int u, int l, int r){
    Tr[u]. Num=a[l];
    If (l==r){
        Return ;
    }
    //lc=u>>1; rc=lc+1;
    Build (lc, l, m);
    Build (rc, m+1, r);
    Tr[u]. Num=tr[lc]. Num+tr[rc]. Num;
}
 Void change (int u, int l, int r, int x, int y, ll k){//区修
    Tr[u]. Num+=(min (r, y)-max (l, x)+1)*k;//经过节点更新 num
    if (x<=l&&y>=r){//覆盖节点就更新 tag
        Tr[u]. Tag+=k;
        Return ;
    }
    Int m=(l+r)>>1;
    If (x<=m){
        Change (lc, l, m, x, y, k);
    }
    If (y>m){
        Change (rc, m+1, r, x, y, k);
    }
}
 Ll query (int u, int l, int r, int x, int y, ll s){//区查，s 路径上 tag 的累计
    if (x<=l&&y>=r){//覆盖就返回
        Return tr[u]. Num+(min (r, y)-max (x, l)+1)*s;
    }
    Ll res=0;
    S+=tr[u]. Tag;//累计 tag，儿子要用
    Int m=(r+l)>>1;
    If (x<=m){
        Res+=query (lc, l, r, x, y, s);
    }
    If (y>m){
        Res+= query (rc, l, r, x, y, s);
    }
    Return res;
}

线段树维护矩阵乘法#

矩阵乘法满足结合律：(A*B)*C=A*(B*C) 分配律：A*(B+C)=A*B+A*C

线段树维护矩阵 - untitled0 - 博客园 (cnblogs.com)

线段树维护哈希#

线段树维护哈希 - zltzlt - 博客园 (cnblogs.com)

线段树

https://www.zzoce.com/blog/线段树/