专题:树状数组及其应用(附线段树模板)

线段树和树状数组其实在暑假就学过,但我当时没理解,也没怎么用过,渐渐地就忘掉了。

之前在做牛客训练营的时候有一道题用到了线段树,于是重新学习了一下线段树

当时以为,只要会了线段树,还学树状数组干啥

知道今天碰到一个题,我才发现树状数组是真香啊

洛谷:P1908 逆序对

原题链接:https://www.luogu.com.cn/problem/P1908

没错,这是一道求逆序对的板子题,数据很强(WA了好几次。。。)

求逆序对可以用朴素算法O(n²)来算(如果数据少的话)

像这个题50万的数据n²肯定不行

逆序对还可以用1、归并排序 2、树状数组 来O(nlogn)求

于是我果断选择了树状数组

树状数组

在学树状数组之前先了解一下这么个东西->lowbit

这是啥呢,lowbit(x)是指x的二进制表达式中最低位的1所对应的值。

比如,6的二进制是0110,所以lowbit(6)=2,4的二进制是0100,所以lowbit(4)=4

函数代码:

int lowbit(int x)
{return x&(-x);} 

至于为啥这么算,这么算的巧妙之处是啥(管那么多干啥~)

然后我们来看一下这样一张图片(忘了从哪找的了,侵权删)

原数组A    上面的数组N([ ]里为二进制数,对应1、2、3、4、5、6、7、8)

仔细观察上面这张照片,可以发现啥呢(针对数组N)

每个点所涵盖的长度都是lowbit(x)

每个点加上lowbit(x)后就成了它上面的那个点(反之亦然)

这样我们用树状数组来保存维护区间时

单点修改,求区间值:

修改一个点后,还要继续修改所有覆盖着这个被修改的点的点(有点绕。。。)

代码:

void insertt(int x)
{
    while(x<=n)
    {N[x]++;
    x+=lowbit(x);}
}

区间查询代码:

int query(int x,int y)
{
    x--;
    int ans1=0,ans2=0;
    while(x>0)
    {ans1+=N[x];
    x-=lowbit(x);}
    while(y>0)
    {ans2+=N[y];
    y-=lowbit(y);}
    return ans2-ans1;
} 

至于区间修改,还要引入一个差分数组,多以我选择使用线段树(^_^)

再说说咋用树状数组求逆序对

树状数组主要还是单点修改,区间查询。

而逆序对就是 如果i > j && a[i] < a[j]

所有逆序对的个数就是对每个数而言,求这个数前面比这个数大的数的个数的和

比如对5、2、1、4、3求逆序对

我们倒序处理

首先插入3,此时d[3]=1,,此时逆序对为0,再插入一个4

于是开一个数组d[]

d[i]指的是1-(i-1)这个区间内的数的个数,一开始给d[]数组清零(d数组下标从1开始)

假设求5,2,1,4,3的逆序对,倒着来处理

首先插入3,此时d[3]=1,逆序对为0

再插入4,会发现d[1]~d[3]的区间值为1,那么逆序对就应该加一,按常理来说如果已经是从小到大排好序的,那么轮到4去插入的时候4应该是最小的(因为是倒序嘛),而现在小于4的区间里有数,那这不就是一个逆序对嘛

再之后依次类推。。。

还有这样一个问题,如果给的数差距很大怎么办,比如给个5,2,9999999213,43435

这样的话开不了这么大的数组,因此要离散化

离散化代码在上面那个题的代码中包含:

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll c[500010],a[500010],d[500010],n;
bool cmp(ll x,ll y)
{
    if(a[x]==a[y])
    {
        if(x<y)
        {return 1;}
        return 0;
    }
    return a[x]<a[y];
}
ll lowbit(ll x)
{return x&(-x);}
void insertt(ll x)
{
    while(x<=n)
    {c[x]++;
    x+=lowbit(x);}
}
ll query(ll y)
{
    ll ans2=0;
    while(y>0)
    {ans2+=c[y];
    y-=lowbit(y);}
    return ans2;
}
int main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
    {scanf("%lld",&a[i]);d[i]=i;}
    sort(d+1,d+n+1,cmp);
    ll ans=0;
    for(int i=n;i>=1;i--)
    {
        insertt(d[i]);
        ans+=query(d[i]-1);
    }
    printf("%lld\n",ans);
    return 0;
}

附:线段树模板

#include <bits/stdc++.h>
using namespace std;
struct qq //l r为掌管区间,pre为权值,add为lazy标记
{
    int l,r;
    long long pre,add;
}sum[1000000];
int op,c[500000];
void build(int l,int r,int os)//树的创建
{
    sum[os].l=l;
    sum[os].r=r;
    if(l==r)
    {
     sum[os].pre=c[op];
     op++;
     return;
    }
    int mid=(l+r)/2;
    build(l,mid,os*2);
    build(mid+1,r,os*2+1);
    sum[os].pre=sum[os*2].pre+sum[os*2+1].pre;
}
void spread(int pp)//下放过程
{
    if(sum[pp].add)//如果该节点的lazy标记不为0,那么将该点的lazy值下放到子节点
    {
        sum[pp*2].pre+=sum[pp].add*(sum[pp*2].r-sum[pp*2].l+1);//对左节点的操作
        sum[pp*2+1].pre+=sum[pp].add*(sum[pp*2+1].r-sum[pp*2+1].l+1);//对右节点的操作
        sum[pp*2].add+=sum[pp].add;
        sum[pp*2+1].add+=sum[pp].add;
        sum[pp].add=0;
    }
}
void change(int pp,int x,int y,int z)//区间修改,打lazy标记
{
    if(x<=sum[pp].l && y>=sum[pp].r) //假设要修改(2,8)的值,发现此时节点的管辖区间l,r包括在修改区间之内,给此节点变值并打上lazy标记
    {
        sum[pp].pre+=(long long)z*(sum[pp].r-sum[pp].l+1); //更新值操作
        sum[pp].add+=z; //打上lazy标记
        return;
    }
    spread(pp);//如果发现没有被包含,那就需要继续向下找,考虑儿子所维护的区间可能因为懒标记的存在而没有修改,因此将懒标记下放
    int mid=(sum[pp].l+sum[pp].r)/2; //对节点的管辖区域求中间值,对其儿子再进行查找
    if(x<=mid)
    {
        change(pp*2,x,y,z);
    }
    if(y>mid)
    {
        change(pp*2+1,x,y,z);
    }
    sum[pp].pre=sum[pp*2].pre+sum[pp*2+1].pre;//最终的权值为左右两个儿子权值之和
}
long long ask(int pp,int x,int y)
{
    if(x<=sum[pp].l && y>=sum[pp].r)
    {return sum[pp].pre;}
    spread(pp);
    int mid=(sum[pp].r+sum[pp].l)>>1;
    long long ans=0;
    if(x<=mid)
    {
        ans+=ask(pp*2,x,y);
    }
    if(y>mid)
    {
        ans+=ask(pp*2+1,x,y);
    }
    return ans;
}

123

点赞
  1. suddenly说道:
    QQbrowser Windows 7

    ( ๑´•ω•) ノ(ㆆᴗㆆ)

发表评论

电子邮件地址不会被公开。必填项已用 * 标注