算法提高课汇总

树状数组

基本操作

• 修改某个元素数值.

• 计算前缀和.

两种操作的时间复杂度均为$O(\lg{n})$

数组含义

树状数组的设计思想: 每个前缀和下标$sum(x)$的$x$的二进制形式由若干个$1$构成,
通过以$1$作为划分依据快速求前缀和.

例如$x = 11_{10} = 1011_2$, 树状数组划分方式为:

• $(1010, 1011], (1000, 1010], (0000, 1000]$.

树状数组$tr(x) = \sum_{i = x - lowbit(x) + 1}^{x} a_i$. 其中$lowbit(x)$结果
为$x$二进制表示的最低一位$1$对应的二进制数值.

操作代码

• 计算前缀和

int sum(x)
{
    int res = 0;
    for ( int i = x; i; i -= lowbit(i) ) res += tr[i];
    return res;
}

其计算过程即树状数组的设计思路.

• 修改某个元素

void add(int x, int c)
{//a[x] += c
    for ( int i = x; i <= length; i += lowbit(i)) tr[i] += c;
}

考虑$a_x += c$后对哪些树状数组有影响, 对于$tr(x)$, 其父节点为$x+lowbit(x)$.
(这里如何解释个人还没思路, 之后会回头更新=.=)

初始化

树状数组的初始化有多种方式, 这里介绍$2$种.

1. add(i, a[i]), 直接利用add函数初始化. $O(n\lg{n})$.
2. 通过树状数组定义初始化. 先计算数组前缀和, 接着通过$tr(x) = (x - lowbit(x), x]$
   定义求对应的区间和. $O(n)$.

算法思路

以计算V为例: 用最低点作为集合划分依据, 则所有V被划分为互不相交的$n$个集合.
对于最低点下标为$k$的V, 从左侧和右侧分别任取一个比$k$高的点均可构成V,
根据乘法原理, 第$k$类集合数量为左侧和右侧高于$k$顶点数目的乘积.

实现时从左到右遍历顶点, 每次在高度$y_k$上加$1$, 则对于第$k$个点其左侧高于$y_k$
的点即区间$[y_k + 1, n]$之和. 接着从右向左遍历, 此时区间$[y_k + 1, n]$之和对应
右侧高与$y_k$的顶点数目之和. 两者相乘即第$k$类集合数目.

对于∧, 用最高点作为集合划分依据, 思路类似.

上述操作仅涉及计算前缀和以及修改某个元素, 可用树状数组实现.

代码实现

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll;

const int N = 2e5 + 10;

int n;
int a[N], tr[N];
int lower[N], upper[N]; //lower[i]: 顶点i左侧低于其高度的顶点数目

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

void add(int x, int c)
{
    for ( int i = x; i <= n; i += lowbit(i) )   tr[i] += c;
}

int sum(int x)
{
    int res = 0;
    for ( int i = x; i; i -= lowbit(i) )    res += tr[i];
    return res;
}

int main()
{
    scanf("%d", &n);
    for ( int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);

    for ( int i = 1; i <= n; i ++ )
    {
        int y = a[i];
        upper[i] = sum(n) - sum(y);  //区间[y + 1, n] 左侧
        lower[i] = sum(y - 1);  //区间[1, y - 1] 左侧
        add(y, 1);
    }

    memset(tr, 0, sizeof tr);
    ll res1 = 0, res2 = 0;
    for ( int i = n; i; i -- )
    {
        int y = a[i];
        res1 += (ll)upper[i] * (sum(n) - sum(y)); //左侧 x 右侧
        res2 += (ll)lower[i] * sum(y - 1);
        add(y, 1);
    }
    printf("%lld %lld\n", res1, res2);

    return 0;
}