树状数组

· · 算法·理论

树状数组的实现

使用场景

给定一个长度为 n 的序列，下面进行 q 次操作：

分析

对于操作 1，我们可以将 a_x \rightarrow a_x+k； 对于操作 2，我们直接求出 \sum_{i=l}^{r} a_i 的值。 很明显，对于操作 2，我们可以直接使用前缀和，单次时间复杂度为 \mathcal{O}(1)，但是单次修改会影响后面所有的前缀和，会导致时间复杂度为 \mathcal{O}(n)。而不采用前缀和会导致修改时间复杂度为 \mathcal{O}(1)，区间和为 \mathcal{O}(n)。那么有什么方法可以实现这个呢，当然是有的，我们可以用树状数组。

树状数组的实现

区间和，单点改

定义 c_i=\sum_{j=i-lowbit(i)+1}^i a_j。

lowbit 函数

我们可以用 $x$ 不断让 $x \rightarrow x/2$，并且判断 $x$ 的奇偶性，如果是奇数，那么这一位就是含有 $1$ 的最低位。 :::info[代码] ```cpp int lowbit(int x) { int ans=0; while (x) { if (x&1) return 1<<ans; x>>=1; } } ``` ::: 可以发现时间复杂度为 $\mathcal{O}(log_2 n)$。 那么怎么优化呢。 我们可以发现 $29952$ 的原码是 $111010100000000$。 $29952$ 的补码是 $000101100000000$。可以发现 $lowbit(29952)=111010100000000 \& 000101100000000=2^8=256$。这是因为 $x$ 的补码将所有为全部取反，前面的所有 $0$ 变成 $1$，在最后一位加上 $1$。将会一直进位，直到是 $0$，而这个 $0$ 它原本就是 $1$。所以我们就找到了，时间复杂度为 $\mathcal{O}(1)$。 :::info[代码] ```cpp int lowbit(int x) { return x&-x; } ``` ::: #### add 函数 如果我们要个第 $x$ 个元素加上 $k$，那么我们就要将所有能包含 $x$ 的区间加上 $k$。 :::info[证明] 证明：若第 $i$ 个区间包含第 $x$ 个元素，则第 $i+lowbit(i)$ 个区间也满足包含第 $x$ 个元素。 设 $s=lowbit(s)$，则 $i=k \cdot 2 \cdot s+s$。 $i+lowbit(i)=k \cdot 2 \cdot s+2 \cdot s \because i-lowbit(i)+1 \le x \le i \therefore k \cdot 2 \cdot s \le x \le k \cdot 2 \cdot s + s \therefore k \cdot 2 \cdot s \le x \le k \cdot 2 \cdot s + 2 \cdot s \therefore i+lowbit(i)-lowbit(i+lowbit(i)+1) +1\le x \le i+ lowbit(i)

得证。 ::: 那么每次我们可以 x \rightarrow x+lowbit(x)，在 c_x \rightarrow c_x+k。 :::info[代码]

void add(int x,int k)
{
    while (x<=n)
    {
        c[x]+=k;
        x+=lowbit(x);
    }
}

:::

getsum 函数

每次我们从 x 开始，加上 c_x=\sum_{i=x-lowbit(x)+1}^x，那么从 x \rightarrow x-lowbit(x)，直到 x=0。 :::info[代码]

int getsum(int x)
{
    int sum=0;
    while (x)
    {
        sum+=c[x];
        x-=lowbit(x);
    }
    return sum;
}

:::

综合代码

:::info[代码]

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+100;
int c[N];
int n,m;
int lowbit(int x){return x&-x;}
void add(int x,int k)
{
    while (x<=n)
    {
        c[x]+=k;
        x+=lowbit(x);
    }
}
int getsum(int x)
{
    int ans=0;
    while (x>0)
    {
        ans+=c[x];
        x-=lowbit(x);
    }
    return ans;
}
int main()
{
    cin>>n>>m;
    for (int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        add(i,x);
    }
    while (m--)
    {
        int op;
        cin>>op;
        if (op==1)
        {
            int x,k;
            cin>>x>>k;
            add(x,k);
        }
        if (op==2)
        {
            int x,y;
            cin>>x>>y;
            cout<<getsum(y)-getsum(x-1)<<endl;
        }
    }
}

:::

性质

我们可以发现对于 getsum 函数，这个前缀和是有若干个区间的和，所以需要具有结合律。而两个前缀和相减则需要具有差分性。

归纳一下，应具有：

常见的不具有差分性的几个运算：\max,\min,\gcd,\operatorname{lcm}。

单点查，区间改

众所周知，正常的树状数组可以处理单点改和区间和的操作，而现在要处理区间改该怎么办呢？

如果是正常的一个数组，我们要让它 l \text{到} r 加上 k，我们可以定义差分数组 d，让 d_l \rightarrow d_l+k，d_{r+1} \rightarrow d_{r+1}-k。如果用树状数组操作的话就是 add(l,k),add(r+1,-k)。根据差分的性质，d_i=a_i-a_{i-1}，所以a_i=a_{i-1}+d_i=a_{i-2}+d_{i-1}+d_i= \ldots = \sum_{j=1}^i d_j，所以如果要查询第 x 个元素的话，就是算出第 x 个前缀和，即 getsum(x)。

:::info[代码]

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+100;
int c[N];
int n,m;
int lowbit(int x){return x&-x;}
void add(int x,int k)
{
    while (x<=n)
    {
        c[x]+=k;
        x+=lowbit(x);
    }
}
int getsum(int x)
{
    int ans=0;
    while (x>0)
    {
        ans+=c[x];
        x-=lowbit(x);
    }
    return ans;
}
int main()
{
    cin>>n>>m;
    for (int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        add(i,x);
    }
    while (m--)
    {
        int op;
        cin>>op;
        if (op==1)
        {
            int l,r,k;
            cin>>l>>r>>k;
            add(l,k),add(r+1,-k);
        }
        if (op==2)
        {
            int x;
            cin>>x;
            cout<<getsum(x)<<endl;
        }
    }
}

:::

树状数组的分析

树状数组虽然含有树这个词，但却并不是是一棵标准意义上的树，它没有根节点，更像是个数组。树状数组采用二进制的方法，分成了若干个区间，与线段树从中间分割的方式不同，就使得效率要比线段树快但是有了其他的约束条件。

树状数组的应用

题目

题目描述

在完成了分配任务之后，西部 314 来到了楼兰古城的西部。相传很久以前这片土地上(比楼兰古城还早)生活着两个部落，一个部落崇拜尖刀(‘V’)，一个部落崇拜铁锹(‘∧’)，他们分别用V和∧的形状来代表各自部落的图腾。

西部 314 在楼兰古城的下面发现了一幅巨大的壁画，壁画上被标记出了 N 个点，经测量发现这 N 个点的水平位置和竖直位置是两两不同的。西部 314 认为这幅壁画所包含的信息与这 N 个点的相对位置有关，因此不妨设坐标分别为(1,y1),(2,y2),…,(n,yn),其中 y1~yn 是 1 到 n 的一个排列。

西部 314 打算研究这幅壁画中包含着多少个图腾，其中V图腾的定义如下（注意：图腾的形式只和这三个纵坐标的相对大小排列顺序有关）1 \le i<j<k \le n 且 y_i>y_j,y_j<y_k;而崇拜∧的部落的图腾被定义为 1 \le i<j<k \le n 且 y_i<y_j,y_j>y_k;

西部 314 想知道，这 n 个点中两个部落图腾的数目。因此，你需要编写一个程序来求出V的个数和∧的个数。

输入格式

第一行一个数 n 第二行是 n 个数，分别代表 y1，y2 \ldots yn

输出格式

两个数，中间用空格隔开，依次为V的个数和∧的个数

思路

这是要我们求V和∧的数量，V是上下横坐标都比中点大，∧是都比中点小。

我们可以用树状数组来求数量，每次将位置放到树状数组中，add(y_i,1)，左边的数量就是 getsum(y_i-1)，至于求后面的只需要倒着一遍执行即可。

:::info[代码]

#include<bits/stdc++.h>
using namespace std;
const int N=200100;
int y[N];
long long c[N];
long long s[N][4];
int n;
int lowbit(int x)
{
    return x&-x;
}
void add(int x,int k)
{
    while (x<=n)
    {
        c[x]+=k;
        x+=lowbit(x);
    }
}
long long getsum(int x)
{
    long long sum=0;
    while (x)
    {
        sum+=c[x];
        x-=lowbit(x);
    }
    return sum;
}
int main()
{
    cin>>n;
    for (int i=1;i<=n;i++) cin>>y[i];
    for (int i=1;i<=n;i++)
    {
        s[i][0]=getsum(y[i]-1);
        s[i][1]=getsum(n)-getsum(y[i]);
        add(y[i],1);
    }
    memset(c,0,sizeof(c));
    for (int i=n;i>=1;i--)
    {
        s[i][2]=getsum(y[i]-1);
        s[i][3]=getsum(n)-getsum(y[i]);
        add(y[i],1);
    }
    long long ans1=0,ans2=0;
    for (int i=1;i<=n;i++)
    {
        ans1+=s[i][1]*s[i][3];
        ans2+=s[i][0]*s[i][2];
    }
    cout<<ans1<<" "<<ans2<<endl;
}

:::

题目

题目描述

破解了符文之语，小 FF 开启了通往地下的道路。当他走到最底层时，发现正前方有一扇巨石门，门上雕刻着一幅古代人进行某种活动的图案。而石门上方用古代文写着“神的殿堂”。小 FF 猜想里面应该就有王室的遗产了。但现在的问题是如何打开这扇门……。

仔细研究后，他发现门上的图案大概是说：古代人认为只有智者才是最容易接近神明的。而最聪明的人往往通过一种仪式选拔出来。仪式大概是指，即将隐退的智者为他的候选人写下一串无序的数字，并让他们进行一种操作，即交换序列中相邻的两个元素。而用最少的交换次数使原序列变成不下降序列的人即是下一任智者。

小 FF 发现门上同样有着 n 个数字。于是他认为打开这扇门的秘诀就是找到让这个序列变成不下降序列所需要的最小次数。但小 FF 不会……只好又找到了你，并答应事成之后与你三七分……

输入格式

第一行为一个整数 n，表示序列长度。

第二行为 n 个整数，表示序列中每个元素。

输出格式

一个整数 \mathit{ans}，即最少操作次数。

输入输出样例 #1

输入 #1

4
2 8 0 3

输出 #1

3

说明/提示

数据范围及约定

样例解释

开始序列为 [2,8,0,3]，目标序列为 [0, 2, 3, 8]，可进行三次操作的目标序列：

  1. 交换 (8,0)，序列变成 [2,0,8,3]；
  2. 交换 (2,0)，序列变成 [0,2,8,3]；
  3. 交换 (8,3)，序列变成 [0,2,3,8]。

    思路

    本题问要交换多少次才能使得成为有序的序列。我们可以轻松的用冒泡排序了写暴力。

:::info[冒泡排序]

for (int i=1;i<=n-1;i++)
{
    for (int j=1;j<=n-i;j++)
    {
        if (a[j]>a[j+1])
            swap(a[j],a[j+1]),sum++;
    }
}
cout<<sum;

::: 可以发现，这求出的就是逆序对的个数，如果我们在加入了 x 到树状数组，那么就会产生 getsum(inf)-getsum(x) 个逆序对，而每次则加入 x 的树状数组中。而 x \in [-2^{31},2^{31})，n \le 5 \times 10^5，所以我们没必要用 x来表示，我们可以先离散化，这样就可以用作小标来进行加入和区间和计算了。

:::info[代码]

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+100;
int a[N],c[N];
vector<int>v;
int n;
int lowbit(int x)
{
    return x&-x;
}
void add(int x,int k)
{
    while (x<=n)
    {
        c[x]+=k;
        x+=lowbit(x);
    }
}
int getsum(int x)
{
    int sum=0;
    while (x)
    {
        sum+=c[x];
        x-=lowbit(x);
    }
    return sum;
}
int main()
{
    cin>>n;
    for (int i=1;i<=n;i++) cin>>a[i],v.push_back(a[i]);
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    for (int i=1;i<=n;i++) a[i]=lower_bound(v.begin(),v.end(),a[i])-v.begin()+1;
    long long ans=0;
    for (int i=1;i<=n;i++)
    {
        add(a[i],1);
        ans+=i-getsum(a[i]);        
    }
    cout<<ans;
}

:::