线段树常见操作函数

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

线段树常见操作函数

作者：

保底不歪抽早柚 , 2021-08-02 11:05:38 , 所有人可见 , 阅读 283

0

1

1.1 线段树单点修改和单点查询

//此处可不用线段树,使用数组线性修改和查询结果

1.2 线段树单点修改和区间查询

//https://loj.ac/p/130

#include <iostream>
#include <cstring>
#include <algorithm>

#define MAXN 1000010

using namespace std;

typedef long long ll;
int n,q;
ll a[MAXN];

struct Tree{
    int l;
    int r;
    ll dat;
}tree[4*MAXN];


void pushup(int root)
{
    tree[root].dat=tree[2*root].dat+tree[2*root+1].dat;
}

void build(int root,int l,int r)
{
    tree[root].l=l,tree[root].r=r;
    if(l==r)
    {
        tree[root].dat=a[l];
        return ;
    }
    int mid=(l+r)/2;
    build(2*root,l,mid);
    build(2*root+1,mid+1,r);
    pushup(root);
}

void modify(int root,int pos,ll val)
{
    if(tree[root].l==pos&&tree[root].r==pos)
        tree[root].dat+=val;
    else
    {
        int mid=(tree[root].l+tree[root].r)/2;
        if(pos<=mid)
            modify(2*root,pos,val);
        else modify(2*root+1,pos,val);
        pushup(root);
    }
}

ll query(int root,int l,int r)
{
    if(l<=tree[root].l&&r>=tree[root].r)
        return tree[root].dat;
    else
    {
        int mid=(tree[root].l+tree[root].r)/2;
        if(r<=mid)
            return query(2*root,l,r);
        else if(l>mid)
            return query(2*root+1,l,r);
        else
        {
            ll sum=0;
            sum+=query(2*root,l,r);
            sum+=query(2*root+1,l,r);
            return sum;
        }

    }

}


int main()
{
    scanf("%d %d",&n,&q);
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    build(1,1,n);
    for(int i=1;i<=q;i++)
    {
        ll op,x,y;
        scanf("%lld %lld %lld",&op,&x,&y);
        if(op==1)
            modify(1,x,y);
        else 
            printf("%lld\n",query(1,x,y));
    }
    return 0;
}

1.3 线段树区间修改和单点查询

//https://loj.ac/p/131

#include <iostream>
#include <cstring>
#include <algorithm>

#define MAXN 1000010

using namespace std;

typedef long long ll;

int n,q;
ll a[MAXN];
struct Tree{
    int l;
    int r;
    ll sum;
    ll add;
}tree[4*MAXN];

void pushup(int root)
{
    tree[root].sum=tree[2*root].sum+tree[2*root+1].sum;
}

void pushdown(int root)
{
    if(tree[root].add)
    {
        tree[2*root].add+=tree[root].add;
        tree[2*root+1].add+=tree[root].add;
        tree[2*root].sum+=tree[root].add*(tree[2*root].r-tree[2*root].l+1);
        tree[2*root+1].sum+=tree[root].add*(tree[2*root+1].r-tree[2*root+1].l+1);
        tree[root].add=0;
    }
}

void build(int root,int l,int r)
{
    tree[root].l=l,tree[root].r=r;
    if(l==r)
    {
        tree[root].sum=a[l];
        tree[root].add=0;
        return ;
    }
    int mid=(l+r)/2;
    build(2*root,l,mid);
    build(2*root+1,mid+1,r);
    pushup(root);
}

void modify(int root,int l,int r,int val)
{
    if(l<=tree[root].l&&r>=tree[root].r)
    {
        tree[root].sum+=(tree[root].r-tree[root].l+1)*val;
        tree[root].add+=val;
    }
    else
    {
        pushdown(root);
        int mid=(tree[root].l+tree[root].r)/2;
        if(l<=mid)
            modify(2*root,l,r,val);
        if(r>mid)
            modify(2*root+1,l,r,val);
        pushup(root);
    }

}

ll query(int root,int pos)
{
    if(tree[root].l==pos&&tree[root].r==pos)
        return tree[root].sum;
    pushdown(root);
    int mid=(tree[root].l+tree[root].r)/2;
    if(pos<=mid)
        return query(2*root,pos);
    else return query(2*root+1,pos);
}


int main()
{
    scanf("%d %d",&n,&q);
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    build(1,1,n);
    for(int i=1;i<=q;i++)
    {
        int op;
        scanf("%d",&op);
        if(op==1)
        {
            int l,r;
            ll val;
            scanf("%d %d %lld",&l,&r,&val);
            modify(1,l,r,val);
        }
        else if(op==2)
        {
            int pos;
            scanf("%d",&pos);
            printf("%lld\n",query(1,pos));
        }
    }
    return 0;
}

1.4 线段树区间修改和区间查询

//https://loj.ac/p/132


#include <iostream>
#include <cstring>
#include <algorithm>

#define MAXN 1000010

using namespace std;

typedef long long ll;

int n,q;
ll a[MAXN];

struct Tree{
    int l;
    int r;
    ll sum;
    ll add;
}tree[4*MAXN];

void pushup(int root)
{
    tree[root].sum=tree[2*root].sum+tree[2*root+1].sum;
}

void pushdown(int root)
{
    if(tree[root].add)
    {
        tree[2*root].add+=tree[root].add;
        tree[2*root+1].add+=tree[root].add;
        tree[2*root].sum+=tree[root].add*(tree[2*root].r-tree[2*root].l+1);
        tree[2*root+1].sum+=tree[root].add*(tree[2*root+1].r-tree[2*root+1].l+1);
        tree[root].add=0;
    }
}

void build(int root,int l,int r)
{
    tree[root].l=l,tree[root].r=r;
    if(l==r)
    {
        tree[root].sum=a[l],tree[root].add=0;
        return ;
    }
    int mid=(l+r)/2;
    build(2*root,l,mid);
    build(2*root+1,mid+1,r);
    pushup(root);
}


void modify(int root,int l,int r,ll val)
{
    if(l<=tree[root].l&&r>=tree[root].r)
    {
        tree[root].add+=val;
        tree[root].sum+=val*(tree[root].r-tree[root].l+1);
    }
    else
    {
        pushdown(root);
        int mid=(tree[root].l+tree[root].r)/2;
        if(l<=mid)
            modify(2*root,l,r,val);
        if(r>mid)
            modify(2*root+1,l,r,val);
        pushup(root);
    }
}

ll query(int root,int l,int r)
{
    if(l<=tree[root].l&&r>=tree[root].r)
        return tree[root].sum;
    pushdown(root);
    int mid=(tree[root].l+tree[root].r)/2;
    if(r<=mid)
        return query(2*root,l,r);
    else if(l>mid)
        return query(2*root+1,l,r);
    else
    {
        ll sum=0;
        sum+=query(2*root,l,r);
        sum+=query(2*root+1,l,r);
        return sum;
    }
}



int main()
{
    scanf("%d %d",&n,&q);
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    build(1,1,n);
    for(int i=1;i<=q;i++)
    {
        int op,l,r;
        ll num;
        scanf("%d %d %d",&op,&l,&r);
        if(op==1)
        {
            scanf("%lld",&num);
            modify(1,l,r,num);
        }
        else if(op==2)
            printf("%lld\n",query(1,l,r));
    }


    return 0;
}

1.5 权值线段树和离散化

题目链接

题目描述

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

插入数值 $x$。
删除数值 $x$(若有多个相同的数，应只删除一个)。
查询数值 $x$ 的排名(若有多个相同的数，应输出最小的排名)。
查询排名为 $x$ 的数值。
求数值 $x$ 的前驱(前驱定义为小于 $x$ 的最大的数)。
求数值 $x$ 的后继(后继定义为大于 $x$ 的最小的数)。

注意： 数据保证查询的结果一定存在。

输入格式

第一行为 $n$，表示操作的个数。

接下来 $n$ 行每行有两个数 $opt$ 和 $x$，$opt$ 表示操作的序号($1 \\le opt \\le 6$)。

输出格式

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

数据范围

$1 \\le n \\le 100000$,所有数均在 $\-10^7$ 到 $10^7$ 内。

输入样例：

输出样例：


// Problem: 普通平衡树
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/description/255/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// Date: 2022-07-15 19:32:11
// 
// Powered by CP Editor (https://cpeditor.org)

/**
  * @author  : SDTBU_LY
  * @version : V1.0.0
  * @上联    : ac自动机fail树上dfs序建可持久化线段树
  * @下联    : 后缀自动机的next指针DAG图上求SG函数
**/


#include <iostream>
#include <algorithm>
#include <cstring>

#define MAXN 100010

using namespace std;

typedef long long ll;

int n,tot=0;
int op[MAXN],id[MAXN];
ll a[MAXN],b[MAXN];


struct Tree{
    int l;
    int r;
    int dat;
}tree[4*MAXN];


void pushup(int root)
{
    tree[root].dat=tree[2*root].dat+tree[2*root+1].dat;
}

void build(int root,int l,int r)
{
    tree[root].l=l,tree[root].r=r;
    if(l==r)
    {
        tree[root].dat=0;
        return ;
    }
    int mid=(l+r)/2;
    build(2*root,l,mid);
    build(2*root+1,mid+1,r);
    pushup(root);
}

void modify(int root,int pos,int val)
{
    if(tree[root].l==pos&&tree[root].r==pos)
    {
        tree[root].dat+=val;
        return ;
    }
    int mid=(tree[root].l+tree[root].r)/2;
    if(pos<=mid)
        modify(2*root,pos,val);
    else modify(2*root+1,pos,val);
    pushup(root);

}

int query_rank(int root,int l,int r)
{
    if(l<=tree[root].l&&r>=tree[root].r)
        return tree[root].dat;
    int mid=(tree[root].l+tree[root].r)/2;
    int res=0;
    if(l<=mid)
        res+=query_rank(2*root,l,r);
    if(r>mid)
        res+=query_rank(2*root+1,l,r);
    return res;
}


int k_th(int root,int pos)
{
    if(tree[root].l==tree[root].r)
        return tree[root].l;
    //int mid=(tree[root].l+tree[root].r)/2;
    if(pos<=tree[2*root].dat)
        return k_th(2*root,pos);
    else return k_th(2*root+1,pos-tree[2*root].dat);


}


int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d %lld",&op[i],&a[i]);
        if(op[i]!=4)
            b[++tot]=a[i];
    }

    sort(b+1,b+tot+1);
    tot=unique(b+1,b+tot+1)-(b+1);

    //cout << tot << endl;

    build(1,1,tot);

    for(int i=1;i<=n;i++)
    {
        if(op[i]!=4)
            id[i]=lower_bound(b+1,b+tot+1,a[i])-b;
    }

    for(int i=1;i<=n;i++)
    {
        //cout << id[i]  << "***" << endl;
        if(op[i]==1)
            modify(1,id[i],1);
        else if(op[i]==2)
            modify(1,id[i],-1);
        else if(op[i]==3)
            printf("%d\n",query_rank(1,1,id[i]-1)+1);
        else if(op[i]==4)
            printf("%lld\n",b[k_th(1,a[i])]);
        else if(op[i]==5)
            printf("%lld\n",b[k_th(1,query_rank(1,1,id[i]-1))]);
        else if(op[i]==6)
            printf("%lld\n",b[k_th(1,query_rank(1,1,id[i])+1)]);
    }

    return 0;
}

修改版

// Problem: 普通平衡树
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/description/255/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// Date: 2022-07-15 19:32:11
// 
// Powered by CP Editor (https://cpeditor.org)

/**
  * @author  : SDTBU_LY
  * @version : V1.0.0
  * @上联    : ac自动机fail树上dfs序建可持久化线段树
  * @下联    : 后缀自动机的next指针DAG图上求SG函数
**/


#include <iostream>
#include <algorithm>
#include <cstring>

#define MAXN 100010

using namespace std;

typedef long long ll;

int n,tot=0;
int op[MAXN],id[MAXN];
ll a[MAXN],b[MAXN];


struct Tree{
    int l;
    int r;
    int dat;
}tree[4*MAXN];


void pushup(int root)
{
    tree[root].dat=tree[2*root].dat+tree[2*root+1].dat;
}

void build(int root,int l,int r)
{
    tree[root].l=l,tree[root].r=r;
    if(l==r)
    {
        tree[root].dat=0;
        return ;
    }
    int mid=(l+r)/2;
    build(2*root,l,mid);
    build(2*root+1,mid+1,r);
    pushup(root);
}

void modify(int root,int pos,int val)
{
    if(tree[root].l==pos&&tree[root].r==pos)
    {
        tree[root].dat+=val;
        return ;
    }
    int mid=(tree[root].l+tree[root].r)/2;
    if(pos<=mid)
        modify(2*root,pos,val);
    else modify(2*root+1,pos,val);
    pushup(root);

}

int query(int root,int l,int r)
{
    if(l<=tree[root].l&&r>=tree[root].r)
        return tree[root].dat;
    int mid=(tree[root].l+tree[root].r)/2;
    int res=0;
    if(l<=mid)
        res+=query(2*root,l,r);
    if(r>mid)
        res+=query(2*root+1,l,r);
    return res;
}


int k_th(int root,int pos)
{
    if(tree[root].l==tree[root].r)
        return tree[root].l;
    //int mid=(tree[root].l+tree[root].r)/2;
    if(pos<=tree[2*root].dat)
        return k_th(2*root,pos);
    else return k_th(2*root+1,pos-tree[2*root].dat);


}

int query_rank(int pos)
{
    return query(1,1,pos-1)+1;
}

int query_pre(int pos)
{
    return k_th(1,query(1,1,pos-1));
}

int query_nex(int pos)
{
    return k_th(1,query(1,1,pos)+1);
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d %lld",&op[i],&a[i]);
        if(op[i]!=4)
            b[++tot]=a[i];
    }

    sort(b+1,b+tot+1);
    tot=unique(b+1,b+tot+1)-(b+1);

    //cout << tot << endl;

    build(1,1,tot);

    for(int i=1;i<=n;i++)
    {
        if(op[i]!=4)
            id[i]=lower_bound(b+1,b+tot+1,a[i])-b;
    }

    for(int i=1;i<=n;i++)
    {
        //cout << id[i]  << "***" << endl;
        if(op[i]==1)
            modify(1,id[i],1);
        else if(op[i]==2)
            modify(1,id[i],-1);
        else if(op[i]==3)
            printf("%d\n",query_rank(id[i]));
        else if(op[i]==4)
            printf("%lld\n",b[k_th(1,a[i])]);
        else if(op[i]==5)
            printf("%lld\n",b[query_pre(id[i])]);
        else if(op[i]==6)
            printf("%lld\n",b[query_nex(id[i])]);
    }

    return 0;
}

1.6 权值线段树求逆序对

题目链接

逆序对的其他方法

给定一个长度为 $n$ 的整数数列，请你计算数列中的逆序对的数量。

逆序对的定义如下：对于数列的第 $i$ 个和第 $j$ 个元素，如果满足 $i < j$ 且 $a\[i\] > a\[j\]$，则其为一个逆序对；否则不是。

输入格式

第一行包含整数 $n$，表示数列的长度。

第二行包含 $n$ 个整数，表示整个数列。

输出格式

输出一个整数，表示逆序对的个数。

数据范围

$1 \\le n \\le 100000$，
数列中的元素的取值范围 $\[1,10^9\]$。

输入样例：

6
2 3 4 5 6 1

输出样例：



// Problem: 逆序对的数量
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/790/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// Date: 2022-07-18 10:44:54
// 
// Powered by CP Editor (https://cpeditor.org)

/**
  * @author  : SDTBU_LY
  * @version : V1.0.0
  * @上联    : ac自动机fail树上dfs序建可持久化线段树
  * @下联    : 后缀自动机的next指针DAG图上求SG函数
**/


#include <iostream>
#include <cstring>
#include <algorithm>

#define MAXN 100010

using namespace std;

typedef long long ll;

int n;
struct node{
    int num;
    int pos;
}s[MAXN];

int id[MAXN];
ll res;

int cmp(node a,node b)
{
    if(a.num==b.num)
        return a.pos<b.pos;
    return a.num<b.num;
}


struct Tree{
    int l;
    int r;
    int dat;
}tree[4*MAXN];


void pushup(int root)
{
    tree[root].dat=tree[2*root].dat+tree[2*root+1].dat;
}

void build(int root,int l,int r)
{
    tree[root].l=l,tree[root].r=r;
    if(l==r)
    {
        tree[root].dat=0;
        return ;
    }
    int mid=(l+r)/2;
    build(2*root,l,mid);
    build(2*root+1,mid+1,r);
    pushup(root);
}


void modify(int root,int pos,int val)
{
    if(tree[root].l==pos&&tree[root].r==pos)
    {
        tree[root].dat+=val;
        return ;
    }
    int mid=(tree[root].l+tree[root].r)/2;
    if(pos<=mid)
        modify(2*root,pos,val);
    else modify(2*root+1,pos,val);
    pushup(root);
}

ll query(int root,int l,int r)
{
    if(l<=tree[root].l&&r>=tree[root].r)
        return tree[root].dat;
    int mid=(tree[root].l+tree[root].r)/2;
    ll ans=0;
    if(l<=mid)
        ans+=query(2*root,l,r);
    if(r>mid)
        ans+=query(2*root+1,l,r);
    return ans;
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&s[i].num);
        s[i].pos=i;
    }
    sort(s+1,s+n+1,cmp);
    for(int i=1;i<=n;i++)
        id[s[i].pos]=i;  

    build(1,1,n);

    for(int i=n;i>=1;i--)
    {
        modify(1,id[i],1);
        res+=query(1,1,id[i]-1);
    }    

    printf("%lld\n",res);
    return 0;
}

0 评论

App 内打开