树状数组

李34 · 2022-02-02 15:53:40 · 个人记录

众所周知，树状数组又快又好打，我特别喜欢。

一、基本模板

树状数组本质是维护前缀和，单次查询和修改时间复杂度 O(\log n)，常数极小。空间复杂度O(n)。

树状数组只需要维护一个数组 T 就能实现单点修改和区间查询前缀和的功能。

黑框表示原数组，绿框表示 T 数组，蓝线表示加和关系。

这就是树状数组的模型。每个节点 T_i 表示从 i 这个点开始往前数（包括自己） lowbit(i) 个点的和。

把数组拆成奇偶两段维护前缀异或和即可。

时间复杂度 O(n\log n) 。

3. P1637 三元上升子序列

这道题比逆序对（不如说是顺序对）多了一个，变成了三个。

那么很显然我们可以用树状数组 + 离散化求顺序对。

将每个数顺序对的个数再丢到另一个树状数组里面，再求一个顺序对就行了。

时间复杂度 O(n\log n) 。

4. P1168 中位数

这道题你可以用两个堆秒杀，但是也可以秉承这树状数组的信仰，尝试用树状数组的 K-th 操作求解。

老套路，先离散化，然后维护某个数出现的个数，然后每次求第 (i+1)/2 大的数即可。

不管怎样时间复杂度都是 O(n\log n) 的。

5. P5094 [USACO04OPEN] MooFest G 加强版

这种题已经进行过一些包装了，不像前面的这么裸了。

由于他规定 v 取的是最大值，不难想到按 v 从小到大排序。

每次加入一只奶牛就和其他所有已经加入的奶牛进行计算。

这样不好计算，我们不妨把已经加入的奶牛分成前后两类。一类 X_i 比当前奶牛的坐标小，一类大。

我们先讨论小的奶牛的贡献。根据题意，加入第 i 头奶牛时它前面的奶牛的贡献为：

然而这个式子不好维护，因为对于每一个 i ， X_i - X_j 都是会变化的。我们需要把关于 i 的变量和关于 j 的分开。

我们将式子拆开，令 m_i 为比 i 坐标小的奶牛的个数，那么式子变为：

v_i\times (m_i\times X_i - \sum_{X_j < X_i} X_j)

这时就好搞了。 v_i 已知， m_i 可以用树状数组维护， \sum_{X_j < X_i} X_j 也可以开一个树状数组维护。

大的奶牛同理，自己推一下。

两个树状数组，时间复杂度 O(n\log n) 。

6. P8087 『JROI-5』Interval

这道题用树状数组不是正解，但是拿来练树状数组还是很有意思的。

而且我在比赛的时候用树状数组过了 。

和逆序对实现较为相似，用树状数组维护 01 序列前缀和。

我们通过初步分析可以发现，由于题目说区间要尽量短，所以以 i 为右端点的区间的左端点肯定是 [1,i] 中最靠前的那一个。

如何判断 [1,i] 都出现过呢？用树状数组维护 01 序列前缀和，那么满足 Query(i) = i 的数就可以当右端点了。

这道题有点怪（应该说我的解法很怪），可以看代码消化一下。

可见树状数组的常数多低，n=4e6 都没卡掉。

时间复杂度 O(n\log n) 。

参考代码：

#include<cstdio>
#define gc getchar
#define max(x,y) (x>y?x:y)
using namespace std;
const int N=4e6+1;
inline int read(){
    int num=0;char ch=gc();
    while (ch>57||ch<48) ch=gc();
    while (ch<58&&ch>47) num=(num<<1)+(num<<3)+(ch^48),ch=gc();
    return num;
}
int n,T[N];
int P[N],B[N],maxn;
inline void Add(int x){
    for (;x<=n;x+=x&-x) ++T[x];
}
inline int Query(int x){
    int res=0;for (;x;x-=x&-x) res+=T[x];return res;
}
int main(){
    n=read();
    int pos=1;
    for (int i=1;i<=n;++i){
        int x=read();
        int y=x;
        while (y<=n&&!P[y]) P[y++]=i;
        //将比x大的数的左端点都记为x 
        Add(x);
        //记录 
        while (pos<=n&&Query(pos)==pos){
            //如果能当右端点就尽量当 
            B[i-P[pos]+1]=max(B[i-P[pos]+1],pos);
            ++pos;
        }
    }
    for (int i=1;i<=n;++i){
        int f=read();
        maxn=max(maxn,B[i]);
        //注意要取max 
        if (maxn>=f){
            printf("%d",i);
            return 0;
        }
    }
    puts("0");
    return 0;
}

7. P5367 【模板】康托展开

结论：1...n 的排列 A 的字典序名次是

P_1 \times (n-1)! + P_2 \times (n-2)! + ...+P_{n-1} \times 1 +1

其中 P_i 表示当前 i 是第几大的没取过的数。

可以发现用树状数组维护很方便就能实现在 O(n\log n) 时间内解决。

当然还有逆康托展开，可以用 K-th 解决。

8. P3605 [USACO17JAN]Promotion Counting P

一道有趣的题目，把逆序对搞到了树上。

很容易想到传统的方法——离散化 + 树状数组——来解决这道题。

不过这道题的难点在于，如果你想像之前一样维护逆序对的话，你得开 n 个树状数组，还不如暴力。

怎么办？我们还是希望能用一颗树状数组维护！

这时就要进行一点点变形。原先的式子为：

ans_i = Query(ord_i - 1)

但是这样会把祖先也给算入你的下属中。我们可以在到达这个节点时先让 ans_i -= Query(ord_i - 1) ，再遍历子节点，然后再 ans_i += Query(ord_i - 1) 。

这样就相当于先把祖先贡献减掉，再把所有贡献全部加上，相当于就是加了儿孙的贡献。这告诉我们割补法也是一种很好的思维方式——当正向行不通时，反过来说不定就是一片新大陆！

时间复杂度仍旧是 O(n\log n) 。

9. P8251 [NOI Online 2022 提高组] 丹钓战

见 题解

10. P5677 [GZOI2017]配对统计

和上一题有异曲同工之妙。

关键就是想到按询问的 r 排序。这点想到就很好做了。

首先我们可以发现如果直接一坨丢进树状数组是很麻烦的。我们不知道数据之间的位置关系。

于是我们可以按询问的 r 排序。这样就只需要处理前一半了。

参考代码：

#include<cstdio>
#include<algorithm>
#define gc getchar
#define lowbit(x) ((x)&-(x))
typedef long long LL;
using namespace std;
const int N=3e5+5;
inline int read(){
    int num=0;char ch=gc();
    while (ch>57||ch<48) ch=gc();
    while (ch<58&&ch>47) num=(num<<1)+(num<<3)+(ch^48),ch=gc();
    return num;
}
struct node{
    int val,tag;
} A[N];
inline bool cmp1(node a,node b){
    return a.val<b.val;
}
inline bool cmp2(node a,node b){
    return a.tag<b.tag;
}
struct TRI{
    int l,r,tag;
} G[N];
inline bool cmpr(TRI a,TRI b){
    return a.r==b.r?a.l<b.l:a.r<b.r;
}
int n,m;
LL T[N];
int ord[N],minn[N],B[N],Rank[N];
inline void Add(int x,int y){
    B[x]+=y;
    for (;x<=n;x+=lowbit(x)) T[x]+=y;
}
inline LL Query(int x){
    LL res=0;
    for (;x;x-=lowbit(x)) res+=T[x];
    return res;
}
int main(){
    n=read(),m=read();
    if (n==1) return puts("0"),0;
    for (int i=1;i<=n;++i) A[i].val=read(),A[i].tag=i;
    //input
    sort(A+1,A+1+n,cmp1);
    minn[1]=1,minn[n]=0;
    for (int i=1;i<=n;++i){
        ord[A[i].tag]=i;
        Rank[i]=A[i].tag;
        if (i==1||i==n) continue;
        if (A[i].val-A[i-1].val<A[i+1].val-A[i].val) minn[i]=0;
        else if (A[i].val-A[i-1].val>A[i+1].val-A[i].val) minn[i]=1;
        else minn[i]=2;
    }
    //离散化+记录前后驱 
    sort(A+1,A+1+n,cmp2);
    //排回来 
    for (int i=1;i<=m;++i) G[i].l=read(),G[i].r=read(),G[i].tag=i;
    sort(G+1,G+1+m,cmpr);
    int nowr=0;
    LL ans=0;
    for (int i=1;i<=m;++i){
        while (nowr<G[i].r){
            //逐个加入 
            ++nowr;
            int now=ord[nowr];
            if (minn[now]==0){
                if (Rank[now-1]<nowr) Add(Rank[now-1],1);
            }
            if (minn[now]==1){
                if (Rank[now+1]<nowr) Add(Rank[now+1],1);
            }
            if (minn[now]==2){
                if (Rank[now-1]<nowr) Add(Rank[now-1],1);
                if (Rank[now+1]<nowr) Add(Rank[now+1],1);
            }
            if (now!=1&&Rank[now-1]<nowr&&(minn[now-1]==2||minn[now-1]==1))
                Add(Rank[now-1],1);
            if (now!=n&&Rank[now+1]<nowr&&(minn[now+1]==2||minn[now+1]==0))
                Add(Rank[now+1],1);
            //分类讨论 
        }
        ans+=(Query(G[i].r)-Query(G[i].l-1))*(LL)G[i].tag;
        //printf("ans=%lld\n",ans);
    }
    printf("%lld",ans);
    return 0;
}/*
4 3
1 2 4 8
2 3
1 4
3 4
*/

从 9,10 两题我们可以总结出一个道理：许多离线题目都可以通过离线存储询问来解决。

很常见的操作就是对询问的左端点或者右端点进行排序，然后将数组里的数逐个加入。

11. 未完待续