数据结构进阶(一)

数据结构进阶(一)

0 在阅读之前

前备知识可看数据结构基础

默认考虑对n个对象进行m次操作的问题,n,m不大于$2 \times 10^5$,数值的绝对值不大于$10^9$,标号从1开始。

区间[l,r]中的数指的是集合 {al,al+1,...,ar}。允许区间退化的情况,即l=r。

1 基本方法

1.1 前缀和

  • 问题:有一个序列a,每次操作给一个区间[l,r],询问[l,r]中数的和。

对于这个问题,可以这样来解答:构造一个序列s满足$s_0=0$,$s_i=s_{i−1}+a_i$,则我们要求的答案为$s_r−s_{l−1}$。序列s称为序列a的前缀和

1.2 差分

  • 问题:有一个序列a,每次操作给出[l,r]和d,将[l,r]中的所有数都加上d。所有操作结束后输出整个序列。

对于这个问题,可以这样解答:构造一个序列b满足$b_i=a_i−a_{i−1}$,则$a_i= \sum_{k=1}^{i} b_i$,即序列a是序列b的前缀和。序列b称为序列a的差分。每次操作将$b_l$加上d,将$b_{r+1}$减去d,则b变为操作后的a的差分。最后用b的前缀和还原a。

前缀和与差分互逆

1.3 二分查找

二分查找也称折半查找,它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。C++内置了与二分查找有关的函数,即algorithm库里的lower_boundupper_bound函数,这两个函数的用法是:

int a[7]={0,1,5,6,6,9,8}
lower_bound(a,a+7,6);    //返回第一个值大于等于6的元素的地址(a+3)
upper_bound(a,a+7,6);    //返回第一个值大于6的元素的地址(a+5)
//找不到就返回a+7

可以看出使用方法应为lower_bound/upper_bound(查找起始地址,查找结束地址的后一个地址,键值)。可以发现函数的返回值减去a(地址)就可以得到该元素的下标。

二分查找函数还可以计算出某值重复的个数:upper_bound(a,a+7,6)-lower_bound(a,a+7,6)

1.4 离散化

离散化,就是把无限空间中有限的个体映射到有限的空间中去,以此提高算法的时空效率。通俗的说,离散化是在不改变数据相对大小的条件下,对数据范围进行相应的缩小。例如:

  • 原数据:1,999,100000,15-------->处理后:1,3,4,2;
  • 原数据:{100,200},{20,50000},{1,400}-------->处理后:{3,4},{2,6},{1,5};

下面谈谈算法竞赛中的离散化。算法竞赛的离散化通常与二分查找相连,可以解决很多标记点值域太大但数组下标不够大的问题。

  • 问题:有一个序列a,每次操作给出l,r,询问a中值在区间[l,r]之间的数的和。(1<=l,r<=$10^9$)

显然这道题不能简单的用数组来写,我们需要缩小值域即离散化之后再用数组进行操作。请看代码。

//a为原数组(离散化数组),b为离散化对照数组,c为映射数组
int a[1000005],b[1000005],c[1000005];
int s[1000005];    //前缀和

int main() 
{
    int n;
    cin>>n;

    for (int i=1;i<=n;i++)
    {
        cin>>a[i];
        b[i]=a[i];
    }

    sort(b+1,b+n+1);
    int m=unique(b+1,b+n+1)-(b+1);    //去重

    for (int i=1;i<=n;i++)    //离散化
    {
        int v=a[i];
        a[i]=lower_bound(b+1,b+m+1,v)-b;
        c[a[i]]+=v;
    }

    for (int i=1;i<=n;i++)
        s[i]=s[i-1]+c[i];

    int l,r;
    cin>>l>>r;

    l=lower_bound(b+1,b+m+1,l)-b;
    r=lower_bound(b+1,b+m+1,r)-b;

    cout<<s[r]-s[l-1]<<'\n';
}

除了上面的离散化方法以外,还有一种不去重离散化的方法,适合元素需要重复的问题。请看代码。

int a[500005],r[500005];    //离散化数组

bool cmp(const int &x,const int &y)
{
    return a[x]<a[y];
}

int main()
{
    int n;
    cin>>n;

    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        r[i]=i;
    }
    sort(r+1,r+1+n,cmp);    //离散化
}

注意离散化是一种思想而不是一个模板,只要达到了缩小值域的目的,就可以说是离散化。

1.5 在线与离线

在线是指按输入顺序回答询问,我们正常写题基本都是在线的。常见的在线方法:主席树

离线是指一起处理所有询问,可以先回答后面的询问。常见的离线方法:莫队

2 区间问题

2.1 RMQ问题

  • 问题:有一个序列a,每次操作给一个区间[l,r],询问[l,r]中的数的最小值。

这个问题称为RMQ问题(除了最小值,还包括一个最大值问题)。如何去解决这个问题?

2.2 静态区间查询问题

基本思想是只维护$O(n)$个区间,把任意区间拆成$logn$个已经维护了的区间,再合并这些区间。若合并的复杂度为$O(1)$,则总复杂度为$O(mlogn)$。

2.3 倍增

倍增,通过字面意思来看就是翻倍。这个方法在很多算法中均有应用。

  • 问题:如何用尽可能少的砝码称量出[1,32]之间的所有重量?(只能在天平的一端放砝码)

答案是使用[1,2,4,8,16]这五个砝码,可以称量出[1,31]之间的所有重量。同样,如果要称量[1,127]之间的所有重量,可以使用[1,2,4,8,16,32,64]这七个砝码。每次我们都选择 2的整次幂作砝码的重量,就可以使用极少的砝码个数量出任意我们所需要的重量。

为什么说是极少呢?因为如果我们要量出[1,1023]之间的所有重量,只需要9个砝码,需要量出[1,1048575]之间的所有重量,只需要19个。如果我们的目标重量翻倍,砝码个数只需要增加1。这叫“对数级”的增长速度,因为砝码的所需个数与目标重量的范围的对数成正比。(用3为什么不行?

2.4 RMQ问题的倍增

设:$f_{i,j}=min_{k \in [j,j+2^i)} a_k$,有递推式:

$$ f_{i,j}=min(f_{i−1,j},f_{i−1,j+2^{i−1}}) $$

预处理数组f的复杂度为$O(nlogn)$。对于询问[l,r],设s=⌊log(r−l+1)⌋,则答案为$f_{s,l}$$[l+2^s,r]$的答案的最小值。请看代码。

int f[20][100005];
int a[100005];

int main() 
{
    int n;
    cin>>n;
    for (int i=1;i<=n;i++)
        cin>>f[0][i];

    for (int j=1;j<17;j++)    //初始化
        for (int i=1;i<=n;i++)
            f[j][i]=min(f[j-1][i],f[j-1][i+(1<<(j-1))]);

    int l,r;
    cin>>l>>r;

    int i=l;
    int minn=INT_MAX;
    for (int j=16;~j;j--)
        if (r-l+1&1<<j) 
        {
	    minn=min(minn,f[j][i]);
	    i+=1<<j;
        }
    cout<<minn<<'\n';
}

2.5 ST表

ST表是用于解决可重复贡献问题的数据结构。

可重复贡献问题:是指对于运算$\bigotimes$,满足$x \bigotimes x=x$,则对应的区间询问就是一个可重复贡献问题。例如,最大值有$max(x,x)=x$,最大公约数有$gcd(x,x)=x$,所以RMQ区间GCD问题就是一个可重复贡献问题。区间和就不具有这个性质,如果求区间和的时候采用的预处理区间重叠了,则会导致重叠部分被计算两次,这是我们所不愿意看到的。另外,还必须满足结合律才能使用ST表求解。

继续来看上面的倍增,由于RMQ问题是一个可重复贡献问题,于是$min(f_{s,l},f_{s,r−2^ s+1})$就是答案。只要能$O(1)$算出s,就能$O(1)$处理询问。

int f[20][100005];
int a[100005];

int main() 
{
    int n;
    cin>>n;
    for (int i=1;i<=n;i++)
        cin>>f[0][i];

    for (int j=1;j<17;j++)    //初始化
        for (int i=1;i<=n;i++)
            f[j][i]=min(f[j-1][i],f[j-1][i+(1<<(j-1))]);

    int l,r;
    cin>>l>>r;

    int s=log2(r-l+1);
    cout<<min(f[s][l],f[s][r-(1<<s)+1])<<'\n';
}

ST表不支持修改操作。下面介绍支持修改操作的线段树。

2.6 线段树

线段树就是对一个序列递归地取中点分成两部分形成的分治树。任何以单点为基本单位的分治树都可以适配任意区间,而取中点分治保证了树高为$logn$。合并所有被完整包含的极大区间即可得到目标区间。如图所示。(l,r表示[l,r])

2.7 建树

这里介绍堆式存储的线段树。这种存储形式的线段树的建树很简单。需要创建一个数组f,数组f用来保存我们要求的答案(或者说状态)。将线段树从上到下,从左到右自1开始标号,可以知道满足以下条件:

  • 对于当前区间,它的标号为k
  • 左子区间标号为2*k
  • 右子区间标号为2*k+1
  • 类似满二叉树的编号

根据线段树的结点数目,数组f的大小应当开成序列长度的4倍。如何建树?直接递归建树即可,先递归到区间长度为1,然后将数组a的值赋在数组f上,然后回溯更新。请看代码。

#define P (k<<1)
#define S (P|1)
#define M (i+j>>1)

int a[200005],f[800020];

void update_sum(int k)    //更新
{
    f[k]=f[P]+f[S];
}
void build(int i,int j,int k)    //建树
{
    if (i==j)
        f[k]=a[i];
    else
    {
        build(i,M,P);
        build(M+1,j,S);
        update_sum(k);
    }
}

2.8 单点修改

单点修改就是修改序列某一个位置的值。这个比较简单,只需要找到对应的位置修改值,然后回溯更新即可。维护的区间中发生改变的只有$O(logn)$个。请看代码。

void change_point(int u,int d,int i,int j,int k)
{
    if (i==j)    //找到该点
        f[k]=d;
    else
    {
        if (u<=M)
            change_point(u,d,i,M,P);
        else
            change_point(u,d,M+1,j,S);
        update(k);
    }
}

2.9 区间修改&懒惰标记

区间修改就是修改序列某一个区间的值。对于修改区间[l,r],如果把所有包含在区间[l,r]中的位置都进行单点修改,那么这个时间复杂度是无法承受的。所以需要借助一个懒惰标记

懒惰标记:一个区间拆成的$O(logn)$个区间均为极大区间,只需要标记这些区间,并更新这些区间上面的$O(logn)$个区间。要用到一个区间的时候一定会先经过更大的区间,可以此时再处理标记的信息。每次查询要处理的区间个数并不会改变,如果处理标记的复杂度也为 O(1),则总复杂度不变。一共有两种懒惰标记方式,分别是下放式和永久化。

  • 下放式标记

下面通过一个故事来生动形象的解释什么是下放式标记。

A 有两个儿子,一个是B,一个是C。
有一天A要建一个新房子,没钱。刚好过年嘛,有人要给B和 C红包,两个红包的钱数相同都是1元,然而因为A是父亲所以红包肯定是先塞给A咯~
理论上来讲A应该把两个红包分别给B和C,但是……缺钱嘛,A 就把红包偷偷收到自己口袋里了。
A高兴地说:「我现在有2份红包了!我又多了2元了!哈哈哈~」
但是A知道,如果他不把红包给B和C,那B和C肯定会不爽然后导致家庭矛盾最后崩溃,所以A对儿子B和C说:「我欠你们每人1份1元的红包,下次有新红包给过来的时候再给你们!这里我先做下记录……嗯……我欠你们各1元……」
儿子B,C有点恼怒:「可是如果有同学问起我们我们收到了多少红包咋办?你把我们的红包都收了,我们还怎么装?」
父亲A赶忙说:「有同学问起来我就会给你们的!我欠条都写好了不会不算话的!」
这样B、C才放了心。

如图,假设修改的就是区间[1,2],那么过程就是这样:

  • 修改区间[1,2],给区间[1,2]的数都加上1
  • 一个一个修改区间[1,2]的数太慢了,干脆现给区间[1,2]的值加上2*1,并给区间[1,2]加上个懒惰标记D=2
  • 现在要查询区间[1,1]的和,当前遍历到了区间[1,2]
  • 发现区间[1,2]的懒惰标记D>0,于是下传标记,即将区间[1,2]的懒惰标记D=0,并且给他的子区间[1,1],[2,2]加上懒惰标记D=1(2/1)。

代码怎么写?请看。

long long a[200005];
long long f[800020],b[800020];

void push_down_sum(int k,int i,int j)    //下放式标记
{
    //更新子区间的值
    f[P]+=b[k]*(M-i+1);    
    f[S]+=b[k]*(j-M);
    //给子区间加上懒惰标记
    b[P]+=b[k];
    b[S]+=b[k];
    b[k]=0;
}
void change_Interval_sum(int u,int v,long long d,int i,int j,int k)
{
    if (u<=i&&v>=j)    //当前区间为修改区间的子集时直接修改当前节点的值,然后打标记,结束修改
    {
        f[k]+=(j-i+1)*d;
        b[k]+=d;
        return;
    }

    push_down_sum(k,i,j);

    if (u<=M)
        change_Interval_sum(u,v,d,i,M,P);
    if (v>M)
        change_Interval_sum(u,v,d,M+1,j,S);
    update_sum(k);    //回溯更新
}
  • 永久化标记

不传递标记,而是在查询时合并所有经过的区间上的标记。如果确定懒惰标记不会在中途被加到溢出(即超过了该类型数据所能表示的最大范围),那么就可以将标记永久化。标记永久化可以避免下传懒惰标记,只需在进行询问时把标记的影响加到答案当中,从而降低程序常数。具体如何处理与题目特性相关,需结合题目来写。这也是树套树和可持久化数据结构中会用到的一种技巧。

2.10 区间查询

完成了建树,单点修改,区间修改,现在只剩下最后一个区间查询了。区间查询与区间修改写法类似,不过多介绍。

long long ask_sum(int u,int v,int i,int j,int k)
{
    if (u<=i&&v>=j)    //当前区间为修改区间的子集时直接返回其值
        return f[k];

    push_down_sum(k,i,j);

    long long sum=0;
    if (u<=M)
        sum+=ask_sum(u,v,i,M,P);
    if (v>M)
        sum+=ask_sum(u,v,M+1,j,S);
    return sum;
}

2.11 树状数组

树状数组二元索引树,又以其发明者的名字命名为Fenwick树,是一种用于高效处理对一个存储数字的列表进行更新及求前缀和的数据结构。

将序列长度扩充成最近的2的幂,建线段树,自底向上将每个结点的右儿子删除,这样会剩下n个结点。可以用一个数组来存储,其中下标i存储包含i的最小结点,这个数组就称为树状数组。

树状数组的工作原理是什么?请看下面这张图:

其中del表示删除了的区间。把剩下的每个结点区间的右边界作为下标,那么就可以构成一个树状数组bit。比如根节点区间[1,8]的值可以用bit[8]来表示。你可以得到下面的信息。

  • bit[2]管理的是a[1]&a[2]
  • bit[4]管理的是a[1]&a[2]&a[3]&a[4]
  • bit[6]管理的是a[5]&a[6]
  • bit[8]则管理全部8个数

假如要算区间[1,7]的和,那么由树状数组给出的信息,我们需要计算bit[4]+bit[6]+bit[7](为什么是这样,你细品)。那么就可以设立一个跳跃下标i,它从7开始,我们知道bit[7]只管理a[7],那么就跳跃1步,i就变为6,我们知道bit[6]管理a[6],并且管理2个数,那么就跳跃2步,i就变为4,我们知道bit[4]管理a[4],并且管理4个数,那么就跳跃4步,i就变为1。把途径的bit数组下标的元素的和加起来就得到了我们要的答案。

2.12 Lowbit函数

问题来了,怎么知道bit[i]管理的数是多少呢?这里引入一个lowbit函数

int lowbit(int x) 
{
    //算出x二进制的从右往左出现第一个1以及这个1之后的那些0组成数的二进制对应的十进制的数
    return x&-x;
}

这样就可以算出跳跃的步数,是不是很神奇?

2.13 树状数组操作

我们写的树状数组要支持以下四个操作。

  • 单点修改

如果改变x的值(加上d),需要更新bit[x]并且更新管理它的bit[i],那么就是一直加上步数直到加到n,这些结点都要加上d,比如一共有8个数第3个数要加上k,那么就是c[3]+=k;c[4]+=k;c[8]+=k;。请看代码。

void change_point(int u,int d,int j)    //单点修改
{
    while (u<=j)    //不能越界
    {
        bit[u]+=d;
        u+=lowbit(u);
    }
}
  • 区间查询

求区间[1,y]的和在原理部分已经举例。如果查询x到y区间的和,那么就将区间[1,y]的和减去区间[1,x-1]的和。请看代码。

int ask_sum(int x)    //区间查询
{
    int ans=0;
    while (x>=1)
    {
        ans+=bit[x];
        x-=lowbit(x);
    }
    return ans;
}
  • 区间修改

如果给区间[x,y]加上一个k,那就是x到n都加上一个k,再从y+1到n加上一个-k。这就是一种差分思想,单点修改就相当于差分左修改点为给定的位置,差分右修改点为n+lowbit(n)。因此这与单点修改的写法是一样的,只不过使用方法是这样的:change_interval(x,k,n);change_interval(y+1,-k,n);。请看代码。

void change_interval(int u,int d,int j)    //区间修改
{
    while (u<=j)    //不能越界
    {
        bit[u]+=d;
        u+=lowbit(u);
    }
}
  • 单点查询

还是差分思想,这时候要把bit看作是差分数组。如果给定x查询位置为x的值,那么把bit求区间[1,x]的和就是新x与原x的差值,把这个差值加上原x就是新x的值。请看代码。

int a[500005];    //原数组
int bit[500005];    //现在变成差分树状数组

int ask_sum(int u)    //区间查询
{
    int ans=0;
    while (u>=1)
    {
        ans+=bit[u];
        u-=lowbit(u);
    }
    return ans;
}

int main()
{
    int n,m;
    cin>>n>>m;

    for (int i=1;i<=n;i++)
        cin>>a[i];

    cin>>x;
    cout<<a[x]+ask_sum(x)<<'\n';
}

2.14 树状数组求逆序对

对于给定的一段正整数序列,逆序对就是序列中$a_i>a_j$$i<j$的有序对。现在给你一个正整数序列,求逆序对数。基本思想就是遍历1-n,计算第i个与前i-1个数构成的逆序对数并加入总和。

怎么计算第i个数与前i-1个数构成的逆序对数?设r[i]表示大小顺序为i的元素在序列中的位置。建树状数组,初始化为0。现在按照数据的大小从小到大将数据的值对应的位置的数加1。因此,在循环到第i项时,前i−1项已经加入到树状数组内了,且都比第i项小, 树状数组内在第i项的位置(r[i])后面的都会与第i项构成逆序对,所以第i个数与前i-1个数产生的逆序对数量为i-树状数组区间[1,r[i]]的和。在这个问题中bit[i]表示位置为i的数是否出现(因为只可能为0或者1)

用r[i]表示大小顺序为i的元素在序列中的位置,这是一种离散化(第二种不去重离散化)。请看代码。

#include<bits/stdc++.h>
using namespace std;

int a[500005],bit[500005],r[500005];
long long ans;

bool cmp(const int &x,const int &y)
{
    return a[x]<a[y];
}

int lowbit(int x)
{
    //算出x二进制的从右往左出现第一个1以及这个1之后的那些0组成数的二进制对应的十进制的数
    return x&-x;
}
void change_point(int u,int d,int j)    //单点修改
{
    while (u<=j)    //不能越界
    {
        bit[u]+=d;
        u+=lowbit(u);
    }
}
int ask_sum(int u)    //区间查询
{
    int ans=0;
    while (u>=1)
    {
        ans+=bit[u];
        u-=lowbit(u);
    }
    return ans;
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n;
    cin>>n;

    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        r[i]=i;
    }
    sort(r+1,r+1+n,cmp);

    for(int i=1;i<=n;i++)
    {
        change_point(r[i],1,n);
        ans+=i-ask_sum(r[i]);
    }
    cout<<ans<<'\n';
    return 0;
}

这个方法比归并排序求逆序对慢一些,时间复杂度受排序限制,为$O(nlogn)$

2.15 树状数组解决LIS问题&LNDS问题

  • LIS问题:给定一个数组,求其中最长的上升序列。例如一个数组[1,3,7,4,6,9],它的最长上升子序列是[1,3,4,6,9]。
  • LNDS(本人独创缩写)问题:给定一个数组,求其中最长的不下降序列。

简单动态规划-1.4 LIS问题已经讨论过LIS问题的动态规划做法,这里尝试用树状数组来做一下。

可以发现LIS问题也是一个讲究元素顺序的问题,和逆序对一样。那么我们可以类似一下逆序对的写法。怎么得到以第i个数为结尾的最长上升子序列的长度呢?设r[i]表示大小顺序为i的元素在序列中的位置。建树状数组,初始化为0。对于第i个数,遍历树状数组区间[1,r[i]]间的数,这些数的位置一定后于第i个数,然后寻找以这些数结尾的最长上升子序列的长度的最大值maxn,由于第i个数在这些数后面,所以以第i个数为结尾的最长上升子序列的长度为maxn+1,然后给第i个数的对应位置(r[i])的数加上maxn+1。在这个问题中bit[i]表示以位置为i的数为结尾的最长上升子序列的长度

这里应该同样是第二种离散化。请看代码。

#include<bits/stdc++.h>
using namespace std;

int a[500005],bit[500005],r[500005];
long long ans;

bool cmp(const int &x,const int &y)
{
    return a[x]<a[y];
}

int lowbit(int x)
{
    //算出x二进制的从右往左出现第一个1以及这个1之后的那些0组成数的二进制对应的十进制的数
    return x&-x;
}
void change_point(int u,int d,int j)    //单点修改
{
    while (u<=j)    //不能越界
    {
        bit[u]=max(bit[u],d);
        u+=lowbit(u);
    }
}
int ask_max(int u)    //区间查询
{
    int ans=0;
    while (u>=1)
    {
        ans=max(ans,bit[u]);
        u-=lowbit(u);
    }
    return ans;
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n;
    cin>>n;

    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        r[i]=i;
    }
    sort(r+1,r+n+1,cmp);

    int ans=0;
    for(int i=1;i<=n;i++)
    {
        change_point(r[i],ask_max(r[i])+1,n);
        ans=max(ans,bit[r[i]]);
    }

    cout<<ans<<'\n';
    return 0;
}

你将这份代码编译并运行,其他输入数据可能没有问题,但这样的一组输入数据[5 1 1 1 1 1],按下回车后你惊奇的发现答案是5。不要慌,来仔细分析一下这组数据:

  • 离散化之后r[i]=[1 2 3 4 5]
  • 第1个数:区间[1,1]的最大值为0,那么bit[i]=0+1,maxn=1
  • 第2个数:区间[1,2]的最大值为1,那么bit[i]=1+1,maxn=2
  • 以此类推,最后maxn=5

可以发现,我们实际上是在做LNDS问题!为什么是这样呢?因为我们默许了第i个数一定可以接。所以这里不是第二种离散化,而是第一种离散化。请看代码。

#include<bits/stdc++.h>
using namespace std;

int a[500005],bit[500005],r[500005];
long long ans;

bool cmp(const int &x,const int &y)
{
    return a[x]<a[y];
}

int lowbit(int x)
{
    //算出x二进制的从右往左出现第一个1以及这个1之后的那些0组成数的二进制对应的十进制的数
    return x&-x;
}
void change_point(int u,int d,int j)    //单点修改
{
    while (u<=j)    //不能越界
    {
        bit[u]=max(bit[u],d);
        u+=lowbit(u);
    }
}
int ask_max(int u)    //区间查询
{
    int ans=0;
    while (u>=1)
    {
        ans=max(ans,bit[u]);
        u-=lowbit(u);
    }
    return ans;
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n;
    cin>>n;

    for(int i=1;i<=n;i++)
        cin>>a[i];
    int m=unique(a+1,a+m+1)-a-1;

    for (int i=1;i<=m;i++)
        r[i]=i;
    sort(r+1,r+m+1,cmp);

    int ans=0;
    for(int i=1;i<=m;i++)
    {
        change_point(r[i],ask_max(r[i])+1,m);    //注意这里的m
        ans=max(ans,bit[r[i]]);
    }

    cout<<ans<<'\n';
    return 0;
}

这样,我们就成功的用树状数组解决了LIS问题和LNDS问题。其实仔细思考过程,你会发现这非常像是DP,其实这就是DP,只不过我们用数据结构去优化了它,去掉了多余的子问题求解。

3 线性表进阶

3.1 双指针

双指针就是用两个指针扫描,扫描过程中保持两个指针的距离不超过一个定值。有快慢指针对撞指针两种。

  • 问题1:给一个正整数序列和k,求序列其中的数的和不大于k的区间的个数。

这道题可以用快慢指针来做,先计算序列的前缀和数组s,然后控制两个指针p,q在下标1处,然后开始遍历,如果s[q]-s[p-1]<=s,那么q往右移一步并且计数,反之则p往右移一步。请看代码。

int a[100005],s[100005];

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n,k;
    cin>>n>>k;

    for (int i=1;i<=n;i++)
    {
        cin>>a[i];
        s[i]=s[i-1]+a[i];
    }

    int p=1,q=1;    //双指针
    int cnt=0;    //计数
    while (q<=n)
    {
        if (s[q]-s[p-1]<=k)
            {cnt+=q-p+1; q++;}
        else {p++;}
    }
    cout<<cnt<<'\n';
    return 0;
}

至于对撞指针,也有很多的应用比如双指针快速排序和判断回文数。双指针是线性时间复杂度

3.2 单调队列

维护一个队列,支持以下操作:

  • 在后面插入元素
  • 删除队首,队尾的元素
  • 求序列中元素的最小值(即队首)

因为要使得可以用队首表示序列中元素的最小值,所以在插入元素时,如果该元素比队尾的元素更大,那么该元素可以入队,如果不是,那就删去队尾的元素一直到队尾的元素小于队首的元素或者队列为空然后入队。这样队列中实际存在的元素就是单调递增的,这就叫单调(递增)队列。单调队列常结合双指针使用,它也是线性时间复杂度

  • 问题:给一个序列和一个数 l,对所有长度为 l 的区间,分别求出区间最小值。

这个问题用单调(递增)队列显然非常好写。这里用的是双端队列deque来写,不是双指针。请看代码。

struct node
{
    int h,i;
};
deque<node> q;

void monotonic_queue()
{
    int n,k;    //窗口长度
    cin>>n>>k;

    for (int i=1;i<=n;i++)
    {
        int h;
        cin>>h;
        
        while (!q.empty()&&q.back().h>h)    //不能产生贡献的删掉
            q.pop_back();

        while (!q.empty()&&q.front().i<=i-k)    //过时元素
            q.pop_front();

        q.push_back((node){h,i});
        if (i>=k) cout<<q.front().h<<' ';
    }
}

3.3 单调栈

数据结构基础-3.4 单调栈中已经讨论过,不再过多描述。


感谢浏览😝!

此文章可能会在后续更新,欢迎纠错。