树状数组，线段树一些常见的问题

[[ slider_text ]]

[[ item.c ]]

树状数组，线段树一些常见的问题

发布时间 2023-05-24 作者：zhangminchen 来源：算法小站

线段树 扫描线 树状数组 差分 trie mex

## 树状数组，下标倍增
树状数组实际上是**针对前缀和的优化**，基于下标，倍增求前缀和
![](/media/content_img/fenwicktree01.png)
![](/media/content_img/fenwicktree02.png)

## 树状数组维护差分序列
**问题描述**
有 $$n$$ 个数一开始都是 `0`，需要支持以下操作
*

`1 l r d` 将所有的 $$a_i$$，$$l \leqslant i \leqslant r$$ 都加上 $$d$$
	
*   `2 x` 查询 $$\left(\sum_{i=1}^{x} a_i \right) \bmod 2^{64}$$

**算法分析**
首先考虑 $$a\_i$$，维护 $$a\_i$$ 的差分数组 $$d\_i = a\_i - a\_{i-1}$$
这样对 $$a[l, r]$$ 都加上 $$d$$，相当于将 `d[l] += d`，`d[r+1] -= d`
同时求 $$a_i$$，相当于对维护的树状数组 `d` 求前缀和 `sum(i)`

考虑 $$\sum\_{i=1}^{x} a_i$$，展开后不难发现
$$a_1 = d_1, \ a_2 = d_1 + d_2, \quad \cdots,\quad a_x = d_1 + d_2 + \cdots + d_x$$

```math
\displaystyle
\sum_{i=1}^{x} a_i = x\cdot d_1 + (x-1) \cdot d_2 + \cdots + d_x \\

= \sum_{i =1}^{x} (x+1-i) \cdot d_i = (x+1) \cdot \sum_{i=1}^{x}d_i - \sum_{i = 1}^{x} i\cdot d_i
```
用两个树状数组维护 $$\sum d_i$$ 和 $$\sum i \cdot d_i$$ 即可

## 二维数点
**问题描述**
给定平面上 $$n$$ 个点 $$(x_i, y_i)$$，回答询问，每个询问给定 $$X_1, X_2, Y_1, Y_2$$
考虑由水平轴 $$X_1, X_2$$，纵轴 $$Y_1, Y_2$$ 所围成的矩形区域，有多少个点？

**算法分析**
根据容斥原理，用 $$[x \leqslant X_2, y \leqslant Y_2]$$ 表示 $$(X_2, Y_2)$$ **左下方**有多少个点
可以根据容斥原理，点的个数可以表示为

$$[x \leqslant X_2, y \leqslant Y_2] - [x \leqslant X_1-1, \quad y \leqslant Y_2] - [x \leqslant X_2, \quad y \leqslant Y_1 - 1] + [x \leqslant X_1-1, \quad y \leqslant Y_1-1] \quad \textbf{(1)}$$

由此我们只需要知道，$$[a, b]$$ 是多少即可，即 $$(a, b)$$ 左下方有多少个点？

问题转换成，对于 $$(x, y)$$，求 $$(x, y)$$ 左下方有多少个点，可以用**扫描线**的思想解决，算法设计如下

将点分为两类，一类是查询点，一类是既定点，将所有点综合考虑
$$\textbf{for} \ y \in Y$$，垂直的扫描线沿着 $$y$$ 方向扫描
对于**既定点**，将其对应的 $$x$$ 坐标 $$+1$$，对于**查询点**，只需要求对应的 $$\leqslant x$$ 的前缀和即可，这可以用树状数组维护。
（树状数组维护的是 $$x$$，先对 $$x$$ 一维离散化）

具体来说，将询问点和既定点封装成**事件** `{y, 事件类型, x, 询问编号}`
每一个询问对应公式 $$\textbf{(1)}$$ 中的$$4$$项，$$+$$ 对应事件类型 $$2$$，$$-$$ 对应类型 $$1$$
比如 $$(X_1, X_2, Y_1, Y_2)$$ 就有事件 $$[Y_2, 2, X_2, id]$$ 和事件 $$[Y_2,1,X_1-1, id]$$
特别地，既定点事件类型为 $$0$$，因为如果坐标相同，我们要优先处理既定点的插入
这样设计数据结构，排序之后即可处理

遍历事件，如果是**既定点**，对于此时的 $$x$$ 找到离散化之后的新坐标 $$nx$$，执行 `add(nx, 1)`
如果是**查询点**，对于此时的 $$x$$，找到**最后一个**满足 $$\leqslant x$$ 的点坐标 $$nx$$，执行 `res = sum(nx)`
**查看事件类型**，如果是事件 $$2$$，那么 `ans[id] += res`，否则 `ans[id] -= res`

## 矩形面积并
**问题描述**
给定 $$n$$ 个矩形 $$[X\_{i, 1}, X\_{i, 2}] \times [Y\_{i, 1}, Y\_{i, 2}]$$，即左上角和右下角坐标
问这些矩形的面积并是多少？

**算法分析**
大致思路是扫描线思想，扫 $$y$$，对 $$x$$ 建线段树，离散化 $$x$$ 并维护
每一个矩形可以用两个事件来描述 $$(y_1, x_1, x_2, 1),  (y_2, x_1, x_2, -1)$$，分别表示矩形左右边界
这样我们只要维护上一次的 $$py$$ 和当前事件的 $$y$$，`ans += cover * |y - py|` 即可
其中 `cover` 表示扫描线沿 $$x$$ 轴方向（垂直方向）被覆盖的**实际长度**

> `cover` 应该如何计算呢？
   可以反过来考虑，计算有多少段未被覆盖是不是比较简单？
   实际上，我们每一个事件都会对 $$[x_1, x_2]$$ 执行区间 `+1` 或者 `-1`
   对于扫描线上任意一段 $$[xl, xr]$$，如果有一段**未被覆盖**，那么肯定**这一段的值为 **`0`
   那么，只要统计 `0` **出现的长度** `len`，考虑一整段的长度 `totlen`，`cover = totlen - len`
   另外，在本例中，注意到一段区间中有 `0`，实际上 `0` 是区间的最小值
   所以线段树需要维护**最小值** `minv` 及**最小值出现的长度** `minlen`，区间**原长度** `len`
   
**算法实现**

离散化 `x` 并且对 `x` 建线段树，初始化时，线段树中的节点 `1, 2, ..., n`
  对应的长度分别是 $$[x\_1, x\_2), [x\_2, x\_3), \cdots [x\_{n-1}, x\_n)$$，比如节点 $$i$$
  初始化时 $$\text{minv} = 0, \text{minlen} = \text{len} = |x\_i - x\_{i+1}|$$，此时 `cover = 0`
  `totlen` 为**一整段** $$[x_1, x_n)$$ 长度，`totlen = all_prod().len`
  
* 扫描每个事件，依 $$y$$ 扫描，维护上一个 $$y$$ 位置 $$py$$
  `cover = totlen - all_prod().minlen`，将 `ans += cover * |y - py|`
  
* 把事件加入集合中，执行线段树区间修改 $$[nx_1, nx_2)$$ 的 `minv += 1`
  注意这里的 $$nx$$ 是离散化之后的坐标
  
## 区间不同数之和
**问题描述**
给定 $$n$$ 个数 $$a_1, \cdots, a_n$$，给定 $$q$$ 组询问
每个询问给定区间 $$[l, r]$$，求区间内不同数字之和，同一个数字多次出现算一次

**算法分析一**
对于区间 $$i \in [l, r]$$，我们需要统计**满足条件**的 $$a_i$$
其中 $$pre(i)$$ 表示 $$a_i$$ **上一次出现的位置**
```math
\begin{cases}
pre(i) < l \\
l \leqslant i \leqslant r
\end{cases}
```
这样问题可以转换成对于点 $$(i, pre(i))$$ 的**二维数点**问题
只不过在维护的时候，执行 `add(i, a[i])`，统计的时候求前缀和即可

具体来说，本例的二维数点比较简单，对于每一个问询，只需要用
$$\left<r, l-1\right> - \left<l-1, l-1\right>$$ 来统计答案即可
> $$\left<r, l-1\right>$$ 就表示在 $$(r, l-1)$$ 下方的点的**前缀和**

$$(i, pre(i))$$可以预处理，需要 $$i \in (1\to n)$$ 时维护$$pre(i)$$ 即可
	这些点可以看作**既定点**，我们扫描 $$x$$ 的时候，维护 `add(pre(i), a[i])` 即可
*  对于每个问询，对应两个事件 `[r, l-1, 2]` 和 `[l-1, l-1, 1]`，其中事件类型 `2` 表示减去当前的**前缀和**

> 树状数组不支持 `0` 下标，具体操作的时候可以让 `y` 坐标同时平移一个单位

**算法分析二**
对所有询问离线，将询问**挂载**到右端点 $$r$$ 上
$$r \in (1 \to n)$$ 扫描右端点，尝试维护 `ans[l]`，表示 `[l, r]` 区间不同数的和

考虑 $$r-1 \to r$$ 时，`ans[l]` 如何变化？
*

如果 $$a_r$$ 在 $$[l, r-1]$$ 中没有出现过，那么 `ans[l] += a[r]`
*  否则，`ans[l]` 不变

> 怎么判断 `a[r]` 出现情况？

只要维护 `a[r]` **上一次出现的位置** `a[p]`，执行**区间加** `ans[p+1...r] += a[r]` 即可
询问的答案就是单点查询 `a[l]`
这可以用树状数组维护差分序列很容易解决

## 异或第 k 小（01-trie）
**问题描述**
给定 $$n$$ 个数，回答询问，每次询问给定两个数 $$x, k$$
求 $$a_1 \oplus x, a_2 \oplus x, \cdots, a_n \oplus x$$ 中从小到大排序中第 $$k$$ 小的元素

**算法分析**
考虑这 $$n$$ 个数，每个数的**二进制**表示，并将其插入一棵 `01-trie` 树中
> 因为要统计第 $$k$$ 小，所以`01-trie`中的节点需要维护`sz`，表示这个二进制位**有几个数经过**

具体来说，对每个数**从高位到低位**检查，并且让指针 `p` 从 `root` 往下遍历
假设当前位是 `w`， ` w = {0 或 1}`
*  首先`p->sz += 1`
*  尝试 `p = p->cld[w]`，如果不存在，就**动态开点**

> 接下来考虑 $$\oplus x$$ 的第 $$k$$ 小，这个数 `res` 到底是多少呢？

*  首先，`x` 的二进制表示，从**高位到低位**可以看作一个**二进制路径**
`p` 从 `root` 开始遍历 `01-trie`

*  从高位到低位，先看一下 `res` 在当前位 `j` 能不能等于 `0`
   假设 `x` 的当前位是 `w`,`res` 在当前位如果可以等于 `0`，**必须满足** `p->sz >= k`
   此时 `p = p->cld[w]` 往下走
   
   否则的话，`res` 当前位一定是 `1`，`p` 只能沿着 `p->cld[w^1]` 的方向
   此时需要顺着这个方向找到第几大呢？新的第 `k`大， `k = k - (p->cld[w]->sz)`
   同时标记 `res`在当前位 `j` 一定是 `1`，`res += (1<< j)`
   
最后的 `res` 就是答案

## 区间 mex
**问题描述**
给定 $$n$$ 个数 $$a_1, \cdots, a_n$$，回答 $$q$$ 个询问
每次给定一个区间 $$[l, r]$$，询问这个区间内最小没有出现过的自然数 `mex`

**算法分析**
同样把所有的询问挂载到右端点 $$r$$ 上，$$r \in (1 \to n)$$ 遍历

记 `x = a[r]`，`pos[x]` 为 **`x` 最后一次出现过的位置**，那么对于每个问询 `[l, r]`
实际上我们要找到**最小的`x`**，满足 $$pos(x) < l$$
可以用线段树维护 `pos` 数组，执行线段树二分得到

同时，对于每个位置 $$r$$，线段树还需要执行单点修改 $$pos(a[r]) \to r$$

> 注意这里，`mex`总共就只有 $$n$$ 个数，`mex` 值不会超过 $$n+1$$
   建线段树的时候开 $$n+1$$ 个点足够，另外如果一个数 $$> n$$
   我们直接令其等于 $$n+1$$ 即可，并不影响答案

上一篇：线段树的 STL 实现（区间修改）下一篇：笛卡尔树和一些杂项数据结构

看完文章有啥想法