欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

树状数组的奇妙应用,99%的人都不知道!

程序员文章站 2024-03-02 21:58:52
...

提到树状数组,大多数人的印象是只能求区间的前缀和。然而,树状数组还有很多其他的用法,用来替代线段树可有效降低空间复杂度和代码长度。
贴一份前缀和代码以供参考。

int c[maxn];
int n;//可能的下标最大值
int lowbit(int x)
{
    return x&(-x);
}
void add(int p,int v)//修改单点
{
    while(p<=n)
    {
        c[p]+=v;
        p+=lowbit(p);
    }
}
int prefix_sum(int p)//前缀和
{
    int sum=0;
    while(p)
    {
        sum+=c[p];
        p-=lowbit(p);
    }
    return sum;
}

维护后缀信息

只要把修改操作和查询操作的遍历顺序反过来,就可以存储后缀信息!
原理是c[i]现在存储从i往后数lowbit(i)个位置的信息

void add(int p,int v)
{
    while(p)
    {
        c[p]-=v;
        p+=lowbit(p);
    }
}
int suffix_sum(int p)
{
    int sum=0;
    while(p<=n)
    {
        sum+=c[p];
        p+=lowbit(p);
    }
    return sum;
}

这个实用性并没有想象中的大,因为所有后缀信息问题都可以转换成前缀问题。

维护最值

以维护最大值为例

void insert(int p,int v)
{
    while(p<=n)
    {
        c[p]=max(c[p],v);
        p+=lowbit(p);
    }
}
int prefix_max(int p)
{
    int mx=0;
    while(p)
    {
        mx=max(mx,c[p]);
        p-=lowbit(p);
    }
    return sum;
}

因为最值不满足区间可减性(已知(a,b)和(a,c)的答案不能得出(b,c)的答案),所以只能求前缀的最大值,是不能像线段树一样任意求出(l,r)的最值的。和线段树一样,不能修改。

查询第k大

分析c[i]的实际意义:从c[i]往前数lowbit(i)个的和。lowbit是二进制最后一个1代表的大小,因此我们可以按位讨论第k大数的位置,复杂度O(logn),并不是必须外层二分套里面的查前缀和

int base;
void init()
{
    base=1;
    while(base*2<=n)
        base<<=1;
}
void insert(int p)
{
    while(p<=n)
    {
        c[p]++;
        p+=lowbit(p);
    }
}
int kth(int k)
{
    int p=0;
    for(int step=base;step;step>>=1)
    {
        if(p+step<=n&&k>c[p+step])
        {
            p+=step;
            k-=c[p];
        }
    }
    return p+1;
}

这个只能求所有数据中的第k大,不如线段树灵活。权值线段树可以自定义L,R求L<x<R的第k大的数。而相比于静态的二分,它的优点是可以随时插入和删除元素。这有效填补了set功能中的一个空白。