Catshao

用户名：Catshao

访问量：28854

签　名：

stO KHIN Orz

等　　级
排　　名	161
经　　验	7135
参赛次数	6
文章发表	46
年　　龄	12
在职情况	学生
学　　校	双语
专　　业

　　自我简介：

TA的其他文章

蓝桥杯2020年第十一届省赛真题-整数小拼接
浏览：1474

蓝桥杯2020年第十一届省赛真题-BST插入节点问题
浏览：547

蓝桥杯2020年第十一届省赛真题-八次求和
浏览：556

你可能喜欢

C语言程序设计教程（第三版）课后习题7.1 （Java代码）

【小白向】树状数组详解

　　作者: Catshao　　　　发表时间：2021-02-11 10:32:58 浏览：290　|　评论：0　

[TOC]

# Part -1 前置算法

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

# Part 1 lowbit

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

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

![lowbit样例](http://cat-shao.gitee.io/mypic/lowbitExample.png)

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

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

```c++
long long lowbit(long long x) {
    return x & -x;
}
```

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

![算法笔记lowbit](http://cat-shao.gitee.io/mypic/suanfabijiLowbit.png)

# Part 2 树状数组

## 引入

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

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

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

## 结构

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

![算法笔记BIT](http://cat-shao.gitee.io/mypic/suanfabijiBIT.png)

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

那么，第x项应该存储那几个数呢？这就要取决于`lowbit(x)`了。
```latex
bit[x] =\sum_{i=1}^{lowbit(x)}a[i]
```

看不懂的我换种写法：从1一直加到`lowbit(x)`
```latex
bit[x] = a[1] + a[2] + ... + a[lowbit(x)]
```

![算法笔记BIT](http://cat-shao.gitee.io/mypic/suanfabijiBIT2.png)

### 单个值增加

还是举上面那个例子：

![算法笔记BIT](http://cat-shao.gitee.io/mypic/bitadd.png)

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

![算法笔记BIT](http://cat-shao.gitee.io/mypic/bitaddlatex.png)

可见树状数组设计得十分精妙。将上面的逻辑转换为代码就有：
```cpp
void add(int index, long long value) {
    while (index <= n) {
        node[index] += value;
        index += lowbit(index);
    }
}
```

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

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

### 区间求和

![算法笔记BIT](http://cat-shao.gitee.io/mypic/bitsum.png)

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

![算法笔记BIT](http://cat-shao.gitee.io/mypic/bitsumlatex.png)

转化为代码：
```cpp
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没有树状数组的简单的模板题（难题也没找到），所以在这里我贴一个[洛谷的题](https://www.luogu.com.cn/problem/P3374)

```cpp
//
// 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

## 引入

[你谷的一道题](https://www.luogu.com.cn/problem/P3368)很有意思。

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

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

## 结构

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

![树状数组2](http://cat-shao.gitee.io/mypic/bit2.png)

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

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

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

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

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

### 区间增加

![sumExample](http://cat-shao.gitee.io/mypic/bitsum2.png)

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

前面说过可以用树状数组进行加速，就有如下代码：
```cpp
tree.add(i, k);
tree.add(j + 1, -k);
```

### 单点查询

根据前面的定义，就有：
```latex
a[x] = \sum_{i = 1}^{x} b[i] 
```

```cpp
tree.sum(x);
```

## 代码

为了通过题目，`MAX_N`开到了500100，所以本地运行会出问题，请使用[在线编译器](https://www.dotcpp.com/run/)来跑代码，也可以将MAX_N调小。
```cpp
//
// 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 算法笔记

[这个部分《算法笔记》讲的比较详细。我贴一下讲解](https://cat-shao.gitee.io/mypic/%E7%AE%97%E6%B3%95%E7%AC%94%E8%AE%B0.pdf)：

[![算法笔记](http://cat-shao.gitee.io/mypic/%E7%A6%BB%E6%95%A3%E5%8C%96%E7%AE%97%E6%B3%95%E7%AC%94%E8%AE%B0.png)](https://cat-shao.gitee.io/mypic/%E7%AE%97%E6%B3%95%E7%AC%94%E8%AE%B0.pdf)

## Part 3 - 2 自己的讲解

我们来看一组样例：

`{1, 999999, 666, 12345, 666}`

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

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

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

### 过程

1. 将数据进行排序，排序后的数据有两个特性：
 1. 数据从小到大，大小关系得到保障。
 2. 重复的数据会排在一起，只需要花费`O(1)`的时间就可以判重（使用`map`速度位`O(log n)`）

2. 遍历这个数组，使用一个计数器`count = 0`。
 - 如果当前`a[i]`与前一个`a[i - 1]`不同：
  1. `count ++;`
  2. 在map中记录：`map[a[i]] = count`
  - （上面的语句可以简化为`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}`

### 代码

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

```cpp
//
// 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 楼兰图腾

[又是一道站外题](https://www.acwing.com/problem/content/243/)

读完题后，我们需要对于每一个数字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。

![映射](https://cat-shao.gitee.io/mypic/lltt-ab.gif)

### 操作1、2
下图为操作1`up`

![映射](https://cat-shao.gitee.io/mypic/lltt-up.gif)

下图为操作2`down`

![映射](https://cat-shao.gitee.io/mypic/lltt-down.gif)

得出如下结论：

$$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$$种结果。

```cpp
// 计算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`。

```cpp
//
// 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](https://www.latexlive.com/)编辑器

0.0分

3 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

Catshao

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题7.1 （Java代码）

C二级辅导-统计字符（C语言代码）

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

【小白向】树状数组详解

评论区

精彩推荐

最长单词（C语言代码）

输出正反三角形（C语言代码）格式错误！！！

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

打印十字图（C语言代码）

【偶数求和】（C语言代码）

矩阵的对角线之和（C语言代码）

简单的事情（C语言代码）

10月月赛题解

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

马拦过河卒（C语言代码）

Catshao

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题7.1 （Java代码）

C二级辅导-统计字符 （C语言代码）

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

【小白向】树状数组详解

评论区

精彩推荐

最长单词 （C语言代码）

输出正反三角形 （C语言代码）格式错误！！！

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

打印十字图 （C语言代码）

【偶数求和】 （C语言代码）

矩阵的对角线之和 （C语言代码）

简单的事情 （C语言代码）

10月月赛题解

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

马拦过河卒 （C语言代码）

C二级辅导-统计字符（C语言代码）

　　评论区

最长单词（C语言代码）

输出正反三角形（C语言代码）格式错误！！！

打印十字图（C语言代码）

【偶数求和】（C语言代码）

矩阵的对角线之和（C语言代码）

简单的事情（C语言代码）

马拦过河卒（C语言代码）