本篇题解来自：【小白向】树状数组详解

建议直接去看Part 4，前面的几个part为树状数组详细讲解，而非本题。

Part -1 前置算法

理论上你需要掌握lowbit，但是本文会提到。会的同学请跳过Part 1。

Part 1 lowbit

在学习树状数组之前，我们先来学习lowbit。

lowbit是一种位运算，下面是一个lowbit的例子。

最后一行为(4)10，不是(4)2

如图，lowbit可以将二进制末尾的1以及后面的0甩出来。因为甩出来的数一定是一个1跟着很多个0，所以在不为1的情况下一定是2的整数次幂。
实现lowbit有多种方法，下面的代码是其中一种实现。

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

《算法笔记》中证明了其可行性：

Part 2 树状数组

引入

我们从一个实际问题入手：
- 给我们一个数列，并实现两个操作：
1. 求数列中一个区间的数的和
2. 将数列中的单个数加上一个数。

一个简单地解决方案，就是把每一个数的值都存起来，但是求和就需要挨个做加法，得出时间复杂度：
1. 求和时间复杂度为O(n)
2. 加法时间复杂度为O(1)

那么，能不能将两个时间复杂度平分一下，达到O(logn)呢？

结构

于是，树状数组（Binary Indexed Tree -> BIT）出现了。

我们使用一个数组bit来维护整个树状数组。bit的每一项都要存储前几个数的和，例如上图。

那么，第x项应该存储那几个数呢？这就要取决于lowbit(x)了。

bit[x] =\sum_{i=1}^{lowbit(x)}a[i]

看不懂的我换种写法：从1一直加到lowbit(x)

bit[x] = a[1] + a[2] + ... + a[lowbit(x)]

单个值增加

还是举上面那个例子：

我们现在要将3进行增加（记为add(3, 加数)，下面简称为add(3)），有哪几个值会发生变化呢？图中绿色部分就是需要变化的部分。

可见树状数组设计得十分精妙。将上面的逻辑转换为代码就有：

void add(int index, long long value) {
    while (index <= n) {
        node[index] += value;
        index += lowbit(index);
    }
}

起名为node是因为class名起的是bit

由于树的高度为O(logn)，所以增加时间复杂度为O(logn)。

区间求和

现在我们要对1 ~ 13进行求和（记为sum(13)），蓝色的部分相加就是结果。

转化为代码：

long long sum(int index) {
    long long sum = 0;
    while (index > 0) {
        sum += node[index];
        index -= lowbit(index);
    }
    return sum;
}

由于树的高度为O(logn)，所以求和时间复杂度为O(logn)。

构造树

由于开始时我们说的是给一个数列，所以如何构建一个这样结构的树呢？
最开始全都初始化为0，然后挨个add呗。这种方法效率虽然不及一种高效的方法，但是时间复杂度为O(nlogn)，并不慢。

题目 & 代码

由于dotcpp没有树状数组的简单的模板题（难题也没找到），所以在这里我贴一个洛谷的题

//
// Created by Cat-shao on 2021/2/9.
//
#include <cstdio>
#include <cstring>
using namespace std;

const long long MAX_N = 5000;

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

class BIT {
public:
    long long node[MAX_N], n;

    BIT(int _n) {
        memset(node, 0, sizeof(node));
        n = _n;
    }

    long long sum(int index) {
        long long sum = 0;
        while (index > 0) {
            sum += node[index];
            index -= lowbit(index);
        }
        return sum;
    }

    void add(int index, long long value) {
        while (index <= n) {
            node[index] += value;
            index += lowbit(index);
        }
    }
};

int BITMain()
{
    // https://www.luogu.com.cn/problem/P3374
    int n, m, op, x, y;
    long long value;
    scanf("%d%d", &n, &m);
    BIT tree = BIT(n);
    for (int i = 1; i <= n; ++i) {
        scanf("%lld", &value);
        tree.add(i, value);
    }

    for (int i = 0; i < m; ++i) {
        scanf("%d%d%d", &op, &x, &y);
        if (op == 1) {
            tree.add(x, y);
        } else if (op == 2) {
            printf("%lld\n", (tree.sum(y) - tree.sum(x - 1)));
        }
    }
    return 0;
}

int BITMain2()
{
}

int main()
{
    BITMain();
}

Part 3 树状数组2

引入

你谷的一道题很有意思。

在这道题中，我们需要有两个操作：
1. 单点查询
2. 区间增加

很明显，如果用数组来存，那么查询时间复杂度为O(1)，区间增加为O(n)，能不能平摊一下成O(logn)？

结构

树状数组的底层结构不需要改变。

我们让b数组1 ~ x的和作为输入数组a[x]的值。

a[x] = \sum_{i = 1}^{x} b[i] 

有两点需要注意：
1. 虽然通过b得到a，但是a是输入
2. 我们发现这个求和过程是可以用树状数组从O(n)加速到O(logn)，其本质与树状数组无关，所以就有：

\sum_{i = 1}^{x} b[i]  \Leftrightarrow BIT.sum(x)

b[i] =+ k \Leftrightarrow BIT.add(i, k)

区间增加

我们从图中可以得知，将b[i]增加，可以影响a[i ~ n]。
如果我们要对a增加k到i, j这个区间，那么b[i] += k就可以更改i ~ n，但是我们并不是到n，而是到j，那么我们只需要b[j + 1] += -k，将其抵消掉就可以了。

前面说过可以用树状数组进行加速，就有如下代码：

tree.add(i, k);
tree.add(j + 1, -k);

单点查询

根据前面的定义，就有：

a[x] = \sum_{i = 1}^{x} b[i] 

tree.sum(x);

代码

为了通过题目，MAX_N开到了500100，所以本地运行会出问题，请使用在线编译器来跑代码，也可以将MAX_N调小。

//
// Created by Cat-shao on 2021/2/9.
//
#include <cstdio>
#include <cstring>
using namespace std;

const long long MAX_N = 500100;

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

class BIT {
public:
    long long node[MAX_N], n;

    BIT(int _n) {
        memset(node, 0, sizeof(node));
        n = _n;
    }

    long long sum(int index) {
        long long sum = 0;
        while (index > 0) {
            sum += node[index];
            index -= lowbit(index);
        }
        return sum;
    }

    void add(int index, long long value) {
        while (index <= n) {
            node[index] += value;
            index += lowbit(index);
        }
    }
};

int BITMain2()
{
    // https://www.luogu.com.cn/problem/P3368
    int n, m, op, x, y, k, prev = 0, now;
    scanf("%d%d", &n, &m);
    BIT tree = BIT(n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &now);
        tree.add(i, now - prev);
        prev = now;
    }

    for (int i = 1; i <= m; ++i) {
        scanf("%d", &op);
        if (op == 1) {
            scanf("%d%d%d", &x, &y, &k);
            tree.add(x, k);
            tree.add(y + 1, -k);
        }
        if (op == 2) {
            scanf("%d", &x);
            printf("%d\n", tree.sum(x));
        }
    }
    return 0;
}

int main()
{
    BITMain2();
}

Part 3 离散化

Part 3 - 1 算法笔记

这个部分《算法笔记》讲的比较详细。我贴一下讲解：

Part 3 - 2 自己的讲解

我们来看一组样例：

{1, 999999, 666, 12345, 666}

在某些场景下，我们只需要考虑数之间的关系，而不考虑加起来的总和，我们可以使用离散化来处理这组数据。（离散化与hash不同）

其中，离散化后的数据要满足如下两个特性：
1. 离散化后的数据要满足之前的大小关系。
2. 离散化出现重复数字时不能离散化成多个数字。

离散化实质上是一种映射方式。想到映射，我们可以使用stl中的map<>来描述映射关系。

过程

1. 将数据进行排序，排序后的数据有两个特性：
2. 数据从小到大，大小关系得到保障。

3. 重复的数据会排在一起，只需要花费O(1)的时间就可以判重（使用map速度位O(log n)）

4. 遍历这个数组，使用一个计数器count = 0。

5. 如果当前a[i]与前一个a[i - 1]不同：
6. count ++;
7. 在map中记录：map[a[i]] = count
8. （上面的语句可以简化为map[a[i]] = ++count;）

还是拿上面的例子{1, 999999, 666, 12345, 666}：
1. 排序：{1, 666, 666, 12345, 999999}
2. 按照count赋值后：

1 -> 1,
666 -> 2,
12345 -> 3,
999999 -> 4,

结果：{1, 4, 2, 3, 2}

代码

我没有找到相关的题目。各位有合适的题目请在下方发评论。

//
// Created by Cat-shao on 2021/2/9.
//
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#include <map>
using namespace std;

int main()
{
    // 没找到相关的题目，各位随机应变吧。
    int n, m;
    priority_queue<int, vector<int>, greater<int> > q; // 小根堆
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &m);
        q.push(m); // 堆排序
    }

    map<int, int> data; // 映射表
    int prev = q.top() - 1, now, cnt = 0;
    // 前一个数据，现在的数据，count
    while (!q.empty()) {
        now = q.top();
        q.pop();

        if (now != prev) {
            data[now] = ++cnt; // 映射成count
        }

        prev = now;
    }

    for (map<int, int>::iterator it = data.begin(); it != data.end(); it++) {
        printf("%d -> %d\n", it->first, it->second);
    }
    return 0;
}

Part 4 楼兰图腾

又是一道站外题

读完题后，我们需要对于每一个数字i实现4种操作。
1. 求在i的前面且比i小的数字有多少。
2. 求在i的后面且比i小的数字有多少。
3. 求在i的前面且比i大的数字有多少。
4. 求在i的后面且比i大的数字有多少。

图形∧需要用到1和2，图形v需要用到3和4，这里先分析∧。

我们可以将输入的数组a映射到数组另一个布尔数组b，如果b[i] = true表示在当前a中有i。

操作1、2

下图为操作1up

下图为操作2down

得出如下结论：

$$up[i] = sum(a[i] - 1)$$

$$down[i] = sum(a[i] - 1)$$

可见二者的区别为：up为从1到n，down为从n到1，遍历顺序不同。

操作3、4

如何通过上面两个操作来得到其余两个操作？
题面中标明了不会有重叠数据，那么对于每一个a中的i，前面有i - 1个数字，后面有n - i个数字。这些数字中，不是比i大就是比i小。因此：
1. 在i的前面且比i大的数字 为 前面数字个数 - 比i小的 -> i - 1 - up[i]
2. 在i的后面且比i大的数字 为 后面数字个数 - 比i小的 -> n - i - down[i]

A和V的个数

对于每一个$$y_j$$，假设有m种$$y_i$$，n种$$y_k$$，那么可以组成$$mn$$种结果。

// 计算V有多少个
ans = 0;
for (int i = 1; i <= n; ++i) {
    ans += (i - 1 - up[i]) * (n - i - down[i]);
}
printf("%lld ", ans);

// 计算A有多少个
ans = 0;
for (int i = 1; i <= n; ++i) {
    ans += up[i] * down[i];
}
printf("%lld", ans);

代码

注意：
1. 树状数组需要初始化。
2. 这题卡long long。

//
// Created by Cat-shao on 2021/2/23.
//

#include <cstdio>
#include <cstring>
using namespace std;

const long long MAX_N = 200010;

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

class BIT {
public:
    long long node[MAX_N], n;

    BIT(int _n) {
        memset(node, 0, sizeof(node));
        n = _n;
    }

    long long sum(int index) {
        long long sum = 0;
        while (index > 0) {
            sum += node[index];
            index -= lowbit(index);
        }
        return sum;
    }

    void add(int index, long long value) {
        while (index <= n) {
            node[index] += value;
            index += lowbit(index);
        }
    }
};

int main()
{
    int n, a[MAX_N];
    long long up[MAX_N], down[MAX_N], ans;
    scanf("%d", &n);
    BIT tree = BIT(n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
    }

    memset(tree.node, 0, sizeof(tree.node));
    for (int i = 1; i <= n; ++i) { // 1 ~ n
        up[i] = tree.sum(a[i] - 1);
        tree.add(a[i], 1); // 设置为true
    }

    memset(tree.node, 0, sizeof(tree.node)); // 需要初始化
    for (int i = n; i >= 1; --i) { // n ~ 1
        down[i] = tree.sum(a[i] - 1);
        tree.add(a[i], 1); // 设置为true
    }

//    for (int i = 1; i <= n; ++i) {
//        printf("i:%d up:%lld down:%lld\n", i, up[i], down[i]);
//    }

    // 计算V有多少个
    ans = 0;
    for (int i = 1; i <= n; ++i) {
        ans += (i - 1 - up[i]) * (n - i - down[i]);
    }
    printf("%lld ", ans);

    // 计算A有多少个
    ans = 0;
    for (int i = 1; i <= n; ++i) {
        ans += up[i] * down[i];
    }
    printf("%lld", ans);
}

各位新年快乐！
——Catshao on 2021年除夕

现在开学了，继续给大家更新
——Catshao on 2021/2/27

参考：
1. 《算法笔记》
2. 妈咪叔的latexlive编辑器