线段树（知识篇）

线段树，从入门到入坑 - xyz的小窝 - 洛谷博客 (luogu.com.cn)

如何快速求出一个序列的区间和呢？可以使用前缀和。如何快速求出一个序列的最值呢？可以使用 ST 表。这两种数据结构在建立的时候颇费功夫，但使用的时候效率很高。如果再增加一个需求：时不时的修改序列的值，那么这两种数据结构就无法高效完成了。不过可以使用线段树来解决这类问题。

在基础篇中，我们已经学习了二叉树的有关概念。而线段树是一种特殊的二叉树，它可以将一个线性的序列组织成一个树状的结构，从而可以在对数的时间复杂度下访问序列上的任意一个区间并进行维护。在本章中，将学习线段树的构建方法和一些简单的应用。

引言

线段树，它将一段区间划分为若干 单位区间 ，每一个节点都储存着一个区间。它 功能强大 ，支持区间求和，区间最大值，区间修改，单点修改等操作。它的大致思想是：将一段大区间平均地划分成 2个小区间，每一个小区间都再平均分成 2 个更小区间……以此类推，直到每一个区间的 L 等于 R （这样这个区间仅包含一个节点的信息，无法被划分）。通过对这些区间进行修改、查询，来实现对大区间的修改、查询。可以用线段树维护的问题必须满足 区间加法 ，否则是不可能将大问题划分成子问题来解决的。

例如：

符合区间加法的例子：

数字之和——总数字之和 = 左区间数字之和 + 右区间数字之和

最大公因数(GCD)——总GCD = gcd( 左区间GCD , 右区间GCD );

最大值——总最大值=max(左区间最大值，右区间最大值)

不符合区间加法的例子：

众数——只知道左右区间的众数，没法求总区间的众数

01序列的最长连续零——只知道左右区间的最长连续零，没法知道总的最长连续零

辨析：区间[L,R]指的是下标从L到R的这(R-L+1)个数，而不是指一条连续的线段。

线段树是将每个区间[L,R]分解成[L,M]和[M+1,R] (其中M=(L+R)/2 这里的除法是整数除法，即对结果下取整)

由于树的天然结构，线段树天生可以通过递归来逐步分解。

上图中，每个区间都是一个节点，每个节点存自己对应的区间的统计信息。

线段树的点修改：

每层只有一个节点包含我们要修改的节点，因此每层只需要更新一个节点即可，复杂度是（logn)

区间修改

使用懒标记后，对于那些正好是线段树节点的区间，我们不继续递归下去，而是打上一个懒标记，将来要用到它的子区间的时候，再向下传递。

更新时，我们是从最大的区间开始，递归向下处理。

pushdown操作

它可以把懒标记下传。

设想一下，如果我们要把懒标记下传，应该注意什么呢？

首先，要给子节点打上懒标记。

然后，我们要修改子节点上的值。

最后，不要忘记把这个节点的懒标记清空。

详见代码

区间查询

有了区间修改的经验，区间查询的方法完全类似。

接下来看模板罢

【模板】线段树 1

题目描述

如题，已知一个数列，你需要进行下面两种操作：

将某区间每一个数加上 $k$。
求出某区间每一个数的和。

输入格式

第一行包含两个整数 $n, m$，分别表示该数列数字的个数和操作的总个数。

第二行包含 $n$ 个用空格分隔的整数，其中第 $i$ 个数字表示数列第 $i$ 项的初始值。

接下来 $m$ 行每行包含 $3$ 或 $4$ 个整数，表示一个操作，具体如下：

1 x y k：将区间 $[x, y]$ 内每个数加上 $k$。
2 x y：输出区间 $[x, y]$ 内每个数的和。

输出格式

输出包含若干行整数，即为所有操作 2 的结果。

样例 #1

样例输入 #1

样例输出 #1

1
2
3

11
8
20

提示

对于 $30\%$ 的数据：$n \le 8$，$m \le 10$。
对于 $70\%$ 的数据：$n \le {10}^3$，$m \le {10}^4$。
对于 $100\%$ 的数据：$1 \le n, m \le {10}^5$。

保证任意时刻数列中所有元素的绝对值之和 $\le {10}^{18}$。

【样例解释】

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll N=1e6;
#define rep(i,a,n) for(int i=a;i<=n;i++)
ll a[N];
ll w[N*4];
void pushup(const int u)
{
    w[u]=w[u*2]+w[u*2+1];
    //w[u]是区间和，u*2是左子树，u*2+1是右子树
    //节点表示的区间和等于两个子节点所表示的区间之和。
    //有了这个操作，我们就可以递归的求出每一个节点所表示的信息。
}
void build(const int u,int l,int r)
{
    if(l==r)
    //到达叶子节点
    {
        w[u]=a[l];
        return ;
    }
    int mid=(l+r)/2;
    //将区间分成[l,mid]和[mid+1,r]进行递归构造
    build(u*2,l,mid);
    build(u*2+1,mid+1,r);
    //位运算以便降低时间
    pushup(u);
    //由于子区间的区间和更新当前区间的和
    //你要不断pushup进行更新的意思
}
//单点查询和修改
//我们如果要定位到p这个节点，实际上是需要找到[p,p]
//这个区间，初始时候，左字节点[1,mid]，右边[mid+1,n]
//其中mid=(1+n)>>1
//如果p<=m,就在左子树，向左一路递归就可以
//右子树同理
//如果是修改，就要一路pushup，保证线段树信息的正确性
//就是说一个数字加上某个数时候，就要找到相应的叶子节点
//然后往这个叶子节点的父节点更新区间和，直到根节点为止
//1.单点查询操作
ll query1(int u,int l,int r,int p)
{
//其中u是根节点，l是左边，r是右边，p是要查询的点
if(l==r)
{
    return w[u];
    //到达叶子节点返回值就可以
}
else
{
    int mid=(l+r)/2;
    if(mid>=p)
    //如果查询的位置在左子树
    //就递归查询左子树
{
    return query1(u*2,l,mid,p);
}
else
//反之查询右子树
{
    return query1(u*2+1,mid+1,r,p);
}
}
//由于查询没有对区间和进行修改操作，因此不需要Pushup
}
//2.单点修改操作
ll update1(int u,int l,int r,int p,ll x)
{
    if(l==r)
    {
        w[u]=x;
        //到达叶子节点直接返回即可
    }
    else
    {
        int mid=(l+r)>>1;
        if(mid>=p)
        {
            update1(u*2,l,mid,p,x);
        }
        else
        {
            update1(u*2+1,mid+1,r,p,x);
        }
        pushup(u);
        //更新后要修改当前节点的和
    }
}

//对点的操作到这里就结束了
//下面进入区间查询

//区间查询
//首先假设我们要查询的区间是[l,r]
//如果当前节点代表的区间[L,R]被所询问的区间[l,r]所包含
//l,r就是 查询的区间
//那么直接返回当前区间的区间和
//也即是说L>=r并且R<=r就被包含了就直接包含
//如果两个区间没有交集，直接返回0
//如果没有被包含且两区间有交，则递归左右子节点处理即可
//所以无论我们查询多大的区间，都可以拆成一些（不超过logn）预处理过的子区间，把这些子区间的区间和加起来，就是答案。

//判断[l,r]是否能够完全包含，是的话就直接返回这一块的值
bool inrange(int L,int R,int l,int r)
{
    return (l<=L)&&(R<=r);
    //判断是否包含
}
//跟刚才那个是极端，这个就是毫无交集了
bool outrange(int L,int R,int l,int r)
{
    return (L>r)||(R<l);
    //判断两者的交集是否无解
}
//区间修改
ll lzy[N*4];
//重中之重的部分就是这一块，所谓的区间修改和区间修改相应的查询，都会变化
void maketag(int u,int len,ll x)
{
    lzy[u]+=x;
    //给这个点加上懒标记
    w[u]+=len*x;
    //这个点加上相应的值
}
//懒标记的下放
//肯定要分区间节点，左子树和右子树的下放
//注意要加上长度
void pushdown(int u,int L,int R)
{
    int Mid=(L+R)/2;
    maketag(u*2,Mid-L+1,lzy[u]);
    maketag(u*2+1,R-Mid,lzy[u]);
    lzy[u]=0;
    //tag的下放所以避免重复修改，当前层要清空标记
}
ll query(int u,int L,int R,int l,int r)
{
    if(inrange(L,R,l,r))
    {
        return w[u];
    }
    //和上面一样如果一样就进行包含求和
    else if(!outrange(L,R,l,r))
    {
        int Mid=(L+R)/2;
        //求平均操作
        pushdown(u,L,R);
        //下放操作
        return query(u*2,L,Mid,l,r)+query(u*2+1,Mid+1,R,l,r);
        //直接分左右查询
    }
    else
    {
        return 0;
    }
}
void update(int u,int L,int R,int l,int r,ll x)
{
    if(inrange(L,R,l,r))
    {
        maketag(u,R-L+1,x);
        //直接打上节点
    }
    //包含就直接下放
    else if(!outrange(L,R,l,r))
    {
        int Mid=(L+R)/2;
        pushdown(u,L,R);
        //进行下放，然后进行更新
        update(u*2,L,Mid,l,r,x);
        update(u*2+1,Mid+1,R,l,r,x);
    pushup(u);
    }
}
int main()
{
int n,m;
cin>>n>>m;
rep(i,1,n)
{
    cin>>a[i];
}
build(1,1,n);
rep(i,1,m)
{
    int op,x,y;
    cin>>op;
    ll k;
    if(op==1)
    {
        cin>>x>>y>>k;
        update(1,1,n,x,y,k);
    }
    else
    {
        cin>>x>>y;
        cout<<(query(1,1,n,x,y))<<'\n';
    }
}
}

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
struct node{
    int sum;
    int l,r;
    int add;//懒标记
}tr[N*4];//线段树要开四倍空间哦
int a[N];//原数列
inline void pushup(int x){
    tr[x].sum=tr[2*x].sum+tr[2*x+1].sum;//pushup操作
}
inline void pushudown(int x){
    if(tr[x].add){
        //如果这个节点上有懒标记
        tr[2*x].add+=tr[x].add,tr[2*x+1].add+=tr[x].add;
        //把这个节点的懒标记给他的两个子节点
        tr[2*x].sum+=tr[x].add*(tr[2*x].r-tr[2*x].l+1);
        tr[2*x+1].sum+=tr[x].add*(tr[2*x+1].r-tr[2*x+1].l+1);
        //分别给它的两个子节点修改
        tr[x].add=0;
        //别忘了清空这个节点的懒标记
    }
}
void build(int x,int l,int r){
    //建树操作
    tr[x].l=l,tr[x].r=r,tr[x].add=0;
    if(l==r){
        tr[x].sum=a[l];
        return;
    }
    int mid=(l+r)/2;
    build(2*x,l,mid),build(2*x+1,mid+1,r);
    pushup(x);
}
int query(int x,int l,int r){
    if(l<=tr[x].l&&r>=tr[x].r) return tr[x].sum;
    pushudown(x);//注意，区间查询时也要下懒传标记
    int mid=(tr[x].l+tr[x].r)/2,sum=0;
    if(l<=mid) sum+=query(x*2,l,r);
    if(r>mid) sum+=query(x*2+1,l,r);
    return sum; 
}
void update(int now,int l,int r,int k){
    if(l<=tr[now].l&&r>=tr[now].r){
        //如果查到子区间了
        tr[now].sum+=k*(tr[now].r-tr[now].l+1);//先修改这个区间
        tr[now].add+=k;//然后给它打上懒标记
        //注：这里一定要分清顺序，先修改，再标记！
    }
    else{
        //如果需要继续向下查询
        pushudown(now);//先把懒标记向下传
        int mid=(tr[now].l+tr[now].r)/2;
        //这里很像区间查询
        if(l<=mid) update(now*2,l,r,k);
        if(r>mid) update(now*2+1,l,r,k);
        pushup(now);//最后别忘了pushup一下
    }
}
int n,q;
int main(){
    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>a[i];
    build(1,1,n);
    while(q--){
        int l,r,k,c;
        cin>>c>>l>>r;
        if(c==1){
            cin>>k;
            update(1,l,r,k);
        }
        else cout<<query(1,l,r)<<endl;
    }
    return 0;
}

结构体存储：（相信看完前面的你应该能理解）

用这个模板ac以下树状数组：

【模板】树状数组 1

题目描述

如题，已知一个数列，你需要进行下面两种操作：

将某一个数加上 $x$
求出某区间每一个数的和

输入格式

第一行包含两个正整数 $n,m$，分别表示该数列数字的个数和操作的总个数。

第二行包含 $n$ 个用空格分隔的整数，其中第 $i$ 个数字表示数列第 $i$ 项的初始值。

接下来 $m$ 行每行包含 $3$ 个整数，表示一个操作，具体如下：

1 x k 含义：将第 $x$ 个数加上 $k$
2 x y 含义：输出区间 $[x,y]$ 内每个数的和

输出格式

输出包含若干行整数，即为所有操作 $2$ 的结果。

样例 #1

样例输入 #1

样例输出 #1

1
2

14
16

提示

【数据范围】

对于 $30\%$ 的数据，$1 \le n \le 8$，$1\le m \le 10$；
对于 $70\%$ 的数据，$1\le n,m \le 10^4$；
对于 $100\%$ 的数据，$1\le n,m \le 5\times 10^5$。

数据保证对于任意时刻，$a$ 的任意子区间（包括长度为 $1$ 和 $n$ 的子区间）和均在 $[-2^{31}, 2^{31})$ 范围内。

样例说明：

故输出结果14、16

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
struct node{
    int sum,l,r;//线段树节点的结构体
}tr[N*4];//线段树需要开四倍空间
int a[N];
inline void pushup(int x){
    tr[x].sum=tr[x*2].sum+tr[x*2+1].sum;
}
void build(int x,int l,int r){
    tr[x].l=l,tr[x].r=r;//节点表示区间的左右界
    if(l==r){
        //若l=r，说明这个节点是叶子节点，直接赋值
        tr[x].sum=a[l];//a是原数列
        return;
    }
    int mid=(l+r)/2;//mid表示左右子区间的间隔
    build(x*2,l,mid),build(x*2+1,mid+1,r);//递归建树
    //线段树是完全二叉树，左右子节点可以用x*2,x*2+1表示
    pushup(x);//pushup操作
}
int query(int x,int l,int r){
    //区间查询
    if(tr[x].l>=l&&tr[x].r<=r) 
        return tr[x].sum;//如果该节点的区间被要查找的区间包括了，那么就不用继续找了，直接返回改节点的值就行了
    int mid=(tr[x].l+tr[x].r)/2;
    int sum=0;
    if(l<=mid) sum+=query(x*2,l,r);//如果当前节点在要查找区间左边界的右面，那么递归查找左子树
    if(r>mid) sum+=query(x*2+1,l,r);//如果当前节点在要查找区间右边界的左面，那么递归查找右子树
    return sum;//由此得出了该区间的值，返回即可
}
void change(int now,int x,int k){
    //单点修改
    if(tr[now].l==tr[now].r)
    {
        tr[now].sum+=k;//如果找到了该节点，那么修改它
        return;
    }
    int mid=(tr[now].l+tr[now].r)/2;
    if(x<=mid) change(now*2,x,k);//如果要寻找的节点在当前节点的左侧，就递归左子树
    else change(now*2+1,x,k);//否则递归右子树
    pushup(now);//pushup操作，维护每个节点的sumC++值
}

int n,q;
int main(){
    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>a[i];
    build(1,1,n);//建树
    while(q--){
        int t,b,c;
        cin>>t>>b>>c;
        if(t==1) change(1,b,c);
        else cout<<query(1,b,c)<<endl;
    }
}

【模板】线段树 2

题目描述

如题，已知一个数列，你需要进行下面三种操作：

将某区间每一个数乘上 $x$；
将某区间每一个数加上 $x$；
求出某区间每一个数的和。

输入格式

第一行包含三个整数 $n,q,m$，分别表示该数列数字的个数、操作的总个数和模数。

第二行包含 $n$ 个用空格分隔的整数，其中第 $i$ 个数字表示数列第 $i$ 项的初始值。

接下来 $q$ 行每行包含若干个整数，表示一个操作，具体如下：

操作 $1$：格式：1 x y k 含义：将区间 $[x,y]$ 内每个数乘上 $k$

操作 $2$：格式：2 x y k 含义：将区间 $[x,y]$ 内每个数加上 $k$

操作 $3$：格式：3 x y 含义：输出区间 $[x,y]$ 内每个数的和对 $m$ 取模所得的结果

输出格式

输出包含若干行整数，即为所有操作 $3$ 的结果。

样例 #1

样例输入 #1

样例输出 #1

1
2

17
2

提示

【数据范围】

对于 $30\%$ 的数据：$n \le 8$，$q \le 10$。
对于 $70\%$ 的数据：$n ^3 $，$q ^4$。
对于 $100\%$ 的数据：$1 \le n \le 10^5$，$1 \le q \le 10^5$。

除样例外，$m = 571373$。

（数据已经过加强 ^_）

样例说明：

故输出应为 $17$、$2$（$40 \bmod 38 = 2$）。

本题核心是懒标记的如何处理

很明显乘除都有懒标记

我们该怎样安排懒标记的pushdown顺序呢？

我们考虑 先乘后加 的维护顺序。假设两个懒标记分别是 $ $ 和 $ $，那么一个数值的更新公式可以表示为：

$ = + . $

更新规则

**加上一个新的 $ $：** 新的值会变成：$ = + + {}. $ 这里的 $ {} $ 是新增的加法操作。
**乘上一个新的 $ $：** 新的值会变成：$ = ( {}) + ( {}). $

#include<bits/stdc++.h>
using  namespace std;
#define rep(i, a, n) for (int i = a; i <= n; i++)
//本题需要乘法标记和加法标记
//主要是顺序
using ll=long long;
const int N=1e6+10;
int p;
ll a[N];
ll w[N<<2];
ll lzy_add[N<<2];
ll lzy_mul[N<<2];
void pushup(const int u)
{
    //w[u]是区间和
    w[u]=(w[u<<1]+w[u<<1|1])%p;
}
void build(const int u,int l,int r)
{
    lzy_mul[u]=1;
    if(l==r)
    {
        w[u]=a[l];
        return ;
    }
int mid=(l+r)>>1;
build(u<<1,l,mid);
build(u<<1|1,mid+1,r);
pushup(u);
}
bool Inrange(int L,int R,int l,int r)
{
    return (l<=L&&r>=R);
}
bool outrange(int L,int R,int l,int r)
{
    return (L>r)||(R<l);
}
void maketag(int u,int L,int R,ll x ,int type)
{
    if(type==1)
    {
        (lzy_add[u]*=x)%=p;
        (lzy_mul[u]*=x)%=p;
        (w[u]*=x)%=p;
    }
    else
    {
        (lzy_add[u]+=x)%=p;
        (w[u]+=(R-L+1)*x)%=p;
    }    
}
void pushdown(int u,int L,int R)
{
int Mid=(L+R)/2;
maketag(u<<1,L,Mid,lzy_mul[u],1);
maketag(u << 1, L, Mid, lzy_add[u], 2);
maketag(u << 1|1,  Mid+1,R, lzy_mul[u], 1);
maketag(u<<1|1,Mid+1,R,lzy_add[u],2);
lzy_mul[u]=1;
lzy_add[u]=0;
}
ll query(int u, int L, int R, int l, int r)
{
    if (Inrange(L, R, l, r))
    {
        return w[u]%p;
    }
    else if (!outrange(L, R, l, r)) 
    {
        int Mid = (L + R) / 2;
        pushdown(u, L, R);
        return (((query(u * 2, L, Mid, l, r))%p) + ((query(u * 2 + 1, Mid + 1, R, l, r))%p))%p;
    }
    else
    {
        return 0;
    }
}
void update(int u, int L, int R, int l, int r, ll x,int type)
{
    if (Inrange(L, R, l, r))
    {
        maketag(u, L,R, x,type);
    }
    else if (!outrange(L, R, l, r))
    {
        int Mid = (L + R) / 2;
        pushdown(u, L, R);
        update(u <<1, L, Mid, l, r, x,type);
        update(u<<1|1, Mid + 1, R, l, r, x,type);
        pushup(u);
    }
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n, m;
    cin >> n >> m>>p;
    rep(i, 1, n)
    {
        cin >> a[i];
}
build(1,1,n);
int opt;
rep(i,1,m)
{
cin>>opt;
if(opt==1)
{
    int x,y;
    ll z;

    cin>>x>>y>>z;
    update(1,1,n,x,y,z,1);
}
else if(opt==2)
{
    int x, y;
    ll z;

    cin >> x >> y >> z;
    update(1, 1, n, x, y, z, 2);
}
else
{
    int x,y;
    cin>>x>>y;
    cout<<query(1,1,n,x,y)%p<<'\n';
}
}
}

结构体版本+注释

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
struct node{
    int l,r;
    int sum,add,mul;
}tr[N*4];//线段树开四倍空间
int a[N];
int n,p,m;
inline void pushup(int x){
    tr[x].sum=(tr[2*x].sum+tr[2*x+1].sum)%p;
}
inline void eval(int x,int add,int mul){
    //我们把计算懒标记单独放在这个函数里，否则好多东西挤一块很难看
    tr[x].sum=(tr[x].sum*mul+add*(tr[x].r-tr[x].l+1))%p;
    tr[x].mul=(mul*tr[x].mul)%p;    //先计算乘法懒标记
    tr[x].add=(tr[x].add*mul+add)%p;//再算加法懒标记
}

inline void pushdown(int x){
    //依次计算两个子节点的值和懒标记
    eval(x*2,tr[x].add,tr[x].mul);
    eval(x*2+1,tr[x].add,tr[x].mul);
    tr[x].add=0,tr[x].mul=1;
    //清空懒标记，注意：乘法懒标记要初始化成1
}
void build(int x,int l,int r){
    tr[x].l=l,tr[x].r=r;
    tr[x].add=0,tr[x].mul=1;//乘法懒标记要初始化成1
    if(l==r){
        tr[x].sum=a[l];
        return;
    }
    int mid=(l+r)/2;
    build(x*2,l,mid),build(x*2+1,mid+1,r);//递归建树
    pushup(x);
}
void change(int x,int l,int r,int add,int mul){
    if(l<=tr[x].l&&r>=tr[x].r) eval(x,add,mul);//计算
    else{
        pushdown(x);
        int mid=(tr[x].l+tr[x].r)/2;
        if(l<=mid) change(x*2,l,r,add,mul);
        if(r>mid) change(x*2+1,l,r,add,mul);
        pushup(x);
    }
}
int query(int x,int l,int r){
    if(l<=tr[x].l&&r>=tr[x].r) return tr[x].sum;
    int sum=0;
    pushdown(x); //区间查询时也要pushdown  
    int mid=(tr[x].l+tr[x].r)/2;
    if(l<=mid) sum+=query(x*2,l,r)%p;
    if(r>mid) sum+=query(x*2+1,l,r)%p;
    return sum;
}
int main(){
    int t,g,c,ch;
    cin>>n>>m>>p;
    for(int i=1;i<=n;i++) cin>>a[i];
    build(1,1,n);
    while(m--){
        cin>>ch>>t>>g;
        if(ch==1){
            cin>>c;
            change(1,t,g,0,c);          
        }
        else if(ch==2){
            cin>>c;
            change(1,t,g,c,1);          
        }
        else cout<<query(1,t,g)%p<<endl;
    }
    return 0;
}

介绍一个知识点：标记永久化：

const int N=1e4+10;
struct node{
    int sum,add;
    int l,r;
}tr[N*4];
int a[N];
void build(int x,int l,int r){
    tr[x].l=l,tr[x].r=r;
    if(l==r){
        tr[x].sum=a[l],tr[x].add=0;
        return;
    }
    int mid=(l+r)/2;
    build(x*2,l,mid),build(x*2+1,mid+1,r);
    tr[x].sum=tr[x*2].sum+tr[x*2+1].sum;
    //标记永久化中只有建树时需要用到pushup操作
}
void update(int x,int l,int r,int k)
{
    tr[x].sum+=(min(tr[x].r,r)-max(tr[x].l,l)+1)*k;
    //要取一个交集来加
    if(tr[x].l>=l&&tr[x].r<=r){
        tr[x].add+=k;//给节点打上标记后不用下传。
        return;
    }
    int mid=(tr[x].l+tr[x].r)/2;
    if(l<=mid) update(x*2,l,r,k);
    if(r>mid) update(x*2+1,l,r,k);
}
int query(int x,int l,int r,int add){
    if(tr[x].l>=l&&tr[x].r<=r){
        int s=(tr[x].r-tr[x].l+1)*add;//查询到节点后给这个区间乘上add
        return tr[x].sum+s;
    }
    add+=tr[x].add;//add代表查询经过的懒标记之和    
    int mid=(tr[x].l+tr[x].r)/2,sum=0;
    if(l<=mid) sum+=query(x*2,l,r,add);
    if(r>mid) sum+=query(x*2+1,l,r,add);
    return sum;
}

权值线段树

权值线段树与线段树的不同点在于，线段树维护区间信息，权值线段树维护值域信息。

如图，权值线段树就长这个样子。

现在我们插入一个数44。

每一个包含44的区间都被加上了1。

那么每个区间维护的到底是什么呢？

是这个区间内的数的数量。

这就是权值线段树的原理。

权值线段树可以干很多事情，比如查询第�k小，查找前驱后继等。

模板：

int tr[N*4];
//这就是上文提到过的线段树的另一种写法，因为权值线段树不需要维护区间信息，所以不需要建树的预处理，这种写法就变得很方便。
inline void pushup(int x){
    tr[x]=tr[x*2]+tr[x*2+1];
}
void insert(int x,int l,int r,int k){
    //插入一个数k
    if(l==r){
        tr[x]++;
        return;
    }
    int mid=(l+r)/2;
    if(k<=mid) insert(x*2,l,mid,k);
    else insert(x*2+1,mid+1,r,k);
    pushup(x);
}
void del(int x,int l,int r,int k){
    //删除一个数k
    if(l==r){
        tr[x]--;
        return;
    }
    int mid=(l+r)/2;
    if(k<=mid) del(x*2,l,mid,k);
    else del(x*2+1,mid+1,r,k);
    pushup(x);
}
int query(int x,int l,int r,int ql,int qr){
    //查询ql，qr之间一共有多少个数
    if(l>=ql&&r<=qr) return tr[x];
    int mid=(l+r)/2,sum=0;
    if(ql<=mid) sum=query(x*2,l,mid,ql,qr);
    if(qr>mid) sum+=query(x*2+1,mid+1,r,ql,qr);
    return sum;
}

NK 中学组织同学们去五云山寨参加社会实践活动，按惯例要乘坐火车去。由于 NK 中学的学生很多，在火车开之前必须清点好人数。

初始时，火车上没有学生。当同学们开始上火车时，年级主任从第一节车厢出发走到最后一节车厢，每节车厢随时都有可能有同学上下。年级主任走到第m节车厢时，他想知道前m*节车厢上一共有多少学生。每次提问，m 总会比前一次大。

题目分析

很明显可以用权值线段树做，维护每个区间的数的数量，具体见代码。

#include <bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int tr[N*4];//权值线段树维护的是值域，所以要开n的范围的四倍
inline void pushup(int x){
    tr[x]=tr[x*2]+tr[x*2+1];
}
void insert(int x,int l,int r,int k,int p){
    if(l==r){
        tr[x]+=p;
        return;
    }
    int mid=(l+r)/2;
    if(k<=mid) insert(x*2,l,mid,k,p);
    else insert(x*2+1,mid+1,r,k,p);
    pushup(x);
}
int query(int x,int l,int r,int ql,int qr){
    if(l>=ql&&r<=qr) return tr[x];
    int mid=(l+r)/2,sum=0;
    if(ql<=mid) sum=query(x*2,l,mid,ql,qr);
    if(qr>mid) sum+=query(x*2+1,mid+1,r,ql,qr);
    return sum;
}
int n,k;
int main(){
    cin>>n>>k;
    while(k--){
        char opt;
        int m,p;
        cin>>opt;
        if(opt=='A'){
            cin>>m;
            cout<<query(1,1,n,1,m)<<endl;
        }
        else if(opt=='B'){
            //上车
            cin>>m>>p;
            insert(1,1,n,m,p);
        }
        else{
            //下车
            cin>>m>>p;
            insert(1,1,n,m,-p);
        }
    }
}

查询第k大数

$$ 如果

k小于区间中点，那么也就说明结果为左区间第

k大数。否则，也就说明结果为右区间第

k−l_size_ 大数。 $$

int kth(int x,int l,int r,int k){
    if(l==r) return l;//查到了，返回即可
    int mid=(l+r)/2;
    if(k<=tr[x*2]) return kth(x*2,l,mid,k); C++
    return kth(x*2+1,mid+1,r,k-tr[x*2]);
}

查询一个数的排名

每次把x与当前区间中点mid比较，如果小于等于mid，说明在左区间，向左儿子寻找。如果大于mid，说明在右区间，这时，它的排名要加上左子树的大小（它比整个左子树的数都大）

int rnk(int x,int l,int r,int k){
    if(l==r) return 1;
    int mid=(l+r)/2;
    if(k<=mid) return rnk(x*2,l,mid,k);
    return rnk(x*2+1,mid+1,r,k)+tr[x*2];
}

动态开点代码解决平衡树

【模板】普通平衡树

题目描述

您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：

插入一个数 $x$。
删除一个数 $x$（若有多个相同的数，应只删除一个）。
定义排名为比当前数小的数的个数 $+1$。查询 $x$ 的排名。
查询数据结构中排名为 $x$ 的数。
求 $x$ 的前驱（前驱定义为小于 $x$，且最大的数）。
求 $x$ 的后继（后继定义为大于 $x$，且最小的数）。

对于操作 3,5,6，不保证当前数据结构中存在数 $x$。

输入格式

第一行为 $n$，表示操作的个数,下面 $n$ 行每行有两个数 $\text{opt}$ 和 $x$，$\text{opt}$ 表示操作的序号（$ 1 $）

输出格式

对于操作 $3,4,5,6$ 每行输出一个数，表示对应答案。

样例 #1

样例输入 #1

样例输出 #1

1
2
3

106465
84185
492737

提示

【数据范围】
对于 $100\%$ 的数据，$1\le n \le 10^5$，$|x| \le 10^7$

来源：Tyvj1728 原名：普通平衡树

在此鸣谢

#include <bits/stdc++.h>
using namespace std;
const int N=1e7+10,M=4e5+10;
int tr[M];
int ls[M],rs[M],tot=0;
inline void pushup(int x)
{
    tr[x]=tr[ls[x]]+tr[rs[x]];//动态开点后，就不能用x*2的方式存了，得开lsrs两个数组（或结构体）
}
void insert(int &x,int l,int r,int k,int p){//x是引用形式，方便传值
    if(!x) x=++tot;//动态开点
    //若p为1则插入，若p为-1则删除
    if(l==r)
    {
        tr[x]+=p;
        return;
    }
    int mid=(l+r)/2;
    if(k<=mid) insert(ls[x],l,mid,k,p);
    else insert(rs[x],mid+1,r,k,p);
    pushup(x);
}
int kth(int x,int l,int r,int k){
    if(l==r) return l;//查到了，返回即可
    int mid=(l+r)/2;
    if(k<=tr[ls[x]]) return kth(ls[x],l,mid,k); 
    return kth(rs[x],mid+1,r,k-tr[ls[x]]);
}
int rnk(int x,int l,int r,int k){
    if(l==r) return 1;
    int mid=(l+r)/2;
    if(k<=mid) return rnk(ls[x],l,mid,k);
    return rnk(rs[x],mid+1,r,k)+tr[ls[x]];
}
int n,root;
int main(){
    cin>>n;
    while(n--){
        int opt,x;
        cin>>opt>>x;
        switch(opt){
        case 1:
            insert(root,-N,N,x,1);//因为动态开点的插入写成引用形式，所以需要带进去一个变量
            break;
        case 2:
            insert(root,-N,N,x,-1);//删除
            break;
        case 3:
            cout<<rnk(root,-N,N,x)<<endl;
            break;
        case 4:
            cout<<kth(root,-N,N,x)<<endl;
            break;
        case 5:
            cout<<kth(root,-N,N,rnk(root,-N,N,x)-1)<<endl;
            break;
        case 6:
            cout<<kth(root,-N,N,rnk(root,-N,N,x+1))<<endl;
            break;
        }
    }
}

ZWK线段树

循环实现

两倍空间奇效

普通的线段树，是从上到下处理的。因为对于普通线段树，我们很容易定位根节点，却不容易定位叶子节点。

建树代码

int tr[N*4];//zkw线段树不用维护子区间，直接开数组就行
int n,m;
void build(){
    cin>>n>>m;
    for(int i=n+1;i<=2*n;i++) cin>>tr[i];//直接读入到叶子节点里
    for(int i=n-1;i>=1;i--) tr[i]=tr[i*2]+tr[i*2+1];//自底向上更新
}

单点修改代码

1
2
3

inline void change(int x,int k){//给x加上k
    for(int i=x+=n;i;i/=2) tr[i]+=k;//自底向上更新
}

单点查询代码

1
2
3

inline int query_one(int x){//查询x值
    return tr[x+n];
}

区间查询代码

inline int query(int l,int r){
    int ans=0;
    for(int p=l-1,q=r+1;p/2!=q/2;p/=2,q/=2){
        if(!(p%2)) ans+=tr[p+1];//第一种情况
        if(q%2) ans+=tr[q-1];//第二种情况
    }
    return ans;
}

区间修改代码

void uplate(int l,int r,int k){//给l,r区间内的数加上k
    for(int p=l-1,q=r+1;p/2!=q/2;p/=2,q/=2){
        if(!(p%2)) add[p+1]+=k;
        if(q%2) add[q-1]+=k;
    }
}

单点查询

在有懒标记的情况下，单点查询也变得不同。

首先自底向上累加所有祖宗节点的懒标记，然后再加上本身的值。

单点查询代码

inline int query_one(int x){//查询x值
    int sum=0;
    for(int i=x+=n;i;i/=2) sum+=add[i];
    return tr[x+n]+add[i];
}

可持久化线段树

复用历史版本的节点

核心代码

void build(int &x,int l,int r){
    //建树操作，即第0个版本，所有版本复用的基础
    x=++tot;//可持久化线段树使用动态开点的方式，因此需要有lsrs数组存储左右儿子节点
    if(l==r){
        tr[x]=a[l];
        return;
    }
    int mid=(l+r)/2;
    build(ls[x],l,mid),build(rs[x],mid+1,r);
    //因为x是引用形式，所以会直接给lsrs数组赋值
}
void change(int u,int &x,int l,int r,int k,int p){
    x=++tot;
    tr[x]=tr[u],ls[x]=ls[u],rs[x]=rs[u];
    //复制原节点
    if(l==r){
        tr[x]=p;
        return;
    }
    int mid=(l+r)/2;
    if(k<=mid) change(ls[u],ls[x],l,mid,k,p);//修改左儿子，右儿子直接复用原节点的右儿子
    else change(rs[u],rs[x],mid+1,r,k,p);//同理
}