type
status
password
date
slug
summary
category
URL
tags
icon
ㅤ | 更新 | 查询前缀和 | 查询任意区间 | 空间复杂度 |
树状数组 | ||||
线段树 |
树状数组
树状数组是一种用于高效处理对一个存储数字的列表进行更新及求前缀和的数据结构。通过树状数组我们可以高效地对一个数组进行如下操作：
update(idx, delta)：将num加到位置idx的数字上。该操作为O(log n)时间复杂度。
prefixSum(idx)：求从数组第一个位置到第idx（含idx）个位置所有数字的和。该操作为O(log n)时间复杂度。
rangeSum(from_idx, to_idx)：求从数组第from_idx个位置到第to_idx个位置的所有数字的和。该操作为O(log n)操作。
- 注意：树状数组的下角标是从 1 开始，原数组的下角标通常是从0开始。更新的时候使用
x & (-x)
Binary Indexed Tree
Binary Indexed Tree并不是一棵树，而是将根据数字的二进制表示来对数组中的元素进行逻辑上的分层存储。
图中第一行为原数组，第二到第四行为依次按层填坑的过程。我们需要从左到右，从上到下依次将相应的值填入对应的位置中。最后一行中即为最终所形成的树状数组。
- 以图中第二行，也就是构造树状数组第一层的过程为例，我们首先需要填充的是数组中第一个数字开始，长度为2的指数个数字的区间内的数字的累加和。所以图中分别填充了从第一个数字开始，长度为
2^0, 2^1, 2^2, 2^3的区间和。到此为止这一步就结束了。因为2^4超过了我们原数组的长度范围。
- 下一步我们构造数组的第二层。与上一层类似，我们依然填充余下的空白中从第空白处一个位置算起长度为2的指数的区间的区间和。例如
3-3空白，我们只需填充[3,3]区间的和；再如5-7空白，我们需要填充从5开始，长度为2^0[5,5]，2^1[5,6] 的区间和；再如9-14空白，我们需要填充从9开始，长度为2^0[9-9]，2^1[9,10]，2^2[9,12]的区间和。
- 类似地，第三层我们填充
7-7长度为2^0[7,7]的区间和；11-11长度为2^0[11,11]的区间和；13-14长度为2^0[13,13]，2^1[13,14]。
到此为止，我们已经完全的构造了对应于输入数组的一个树状数组
BIT（方便起见，此处对此数组的索引为从1开始）查询数组的前缀和(每次减去lowbit)
如上图所示，利用图中已构造好的树状数组，计算
id=13 的前缀和：可以发现，在这棵抽象的树向上移动的过程其实就是不断将当前数字的最后一个
1翻转为0的过程。基于这一事实，实现在Binary Indexed Tree中向上（在数组中向前）寻找母结点的代码就非常容易了。例如给定一个int x = 13，这个过程可以用如下运算实现：更新数组中的元素(每次加上lowbit)
当我们更新了原数组中的某一个数字后，显然我们也需要更新Binary Indexed Tree中相应的区间和来应对这一改变。以给原数组中第5个位置的数字加2为例，基于之前构造好的Binary Indexed Tree，更新的过程如下图中所示：
从图中我们发现，从5开始，应当被更新的位置的坐标为原坐标加上原坐标二进制表示中最后一个1所代表的数字。这一过程和上面求和的过程刚好相反。以
int x = 5为例，我们可以用如C++下运算实现：树状数组的初始化
Binary Indexed Tree的建立非常简单。我们只需初始化一个全为0的数组，并对原数组中的每一个位置对应的数字调用一次更新操作即可。这是一个
O(nlogn)的建立过程。- 初始化长度为
n + 1的Binary Indexed Tree数组bit，并将list中的数字对应地放在bit[1]到bit[n]的各个位置。
- 对于 1 到 n 的每一个 i ，进行如下操作：
- 令
j = i + (i & -i)，若j < n + 1，则bit[j] = bit[j] + bit[i]
源码
307. 区域和检索 - 数组可修改 - 力扣（LeetCode）
源码对应版
初始化更容易理解版本
线段树
线段树（segment tree）是用来存放给定区间（segment, or interval）内对应信息的一种数据结构。与树状数组（binary indexed tree）相似，线段树也用来处理数组相应的区间查询（range query）和元素更新（update）操作。与树状数组不同的是，线段树不止可以适用于区间求和的查询，也可以进行区间最大值，区间最小值（Range Minimum/Maximum Query problem）或者区间异或值的查询。对应于树状数组，线段树进行更新（update）的操作为
O(logn)，进行区间查询（range query）的操作也为O(logn)。下面以求最小值为例：如上图所示，线段树是用一个完全二叉树来存储对应于其每一个区间（segment）的数据。该二叉树的每一个结点中保存着相对应于这一个区间的信息。同时，线段树所使用的这个二叉树是用一个数组保存的。
初始化
线段树的初始化是自底向上进行的。从每一个叶子结点开始（也就是原数组中的每一个元素），沿从叶子结点到根结点的路径向上按层构建。在构建的每一步中，对应两个子结点的数据将被用来构建应当存储于它们母结点中的值。这个构建的过程可能依所需要处理的问题不同而不同（例如对于保存区间最小值的线段树来说，merge的过程应为
min()函数，用以取得两个子区间中的最小区间最小值作为当前融合过后的区间的区间最小值）。- 给定一个输入长度为
n的数组array[n]，其所对应的最小值线段树segmentTree的构造过程如下所示：
- 叶子节点：每一个叶结点存储对应于输入数组的每一个节点，
segmentTree[n:2n-1]=array[0:n-1]
- 中间节点：每一个中间结点存储对应于输入数组某一区间
arr[i:j]对应的信息，此处0≤i<j<N。对于线段树中的任意结点i，其左子结点为2*i，右子结点为2*i + 1，其母结点为i/2。segmentTree[i]=min(segmentTree[2*i],segmentTree[2*i+1])
更新
更新一个线段树的过程与上述构造线段树的过程相同。当输入数组中位于
i位置的元素被更新时，我们只需从这一元素对应的叶子结点开始，沿二叉树的路径向上更新至更结点即可。对于线段树中的任意结点i，其左子结点为2*i，右子结点为2*i + 1，其母结点为i/2。查询（记住这部分代码）
区间查询大体上可以分为3种情况讨论：
- 当前结点所代表的区间完全位于给定需要被查询的区间之外，则不应考虑当前结点
- 当前结点所代表的区间完全位于给定需要被查询的区间之内，则可以直接查看当前结点的母结点
- 当前结点所代表的区间部分位于需要被查询的区间之内，部分位于其外，则我们先考虑位于区间外的部分，后考虑区间内的（注意总有可能找到完全位于区间内的结点，因为叶子结点的区间长度为1，因此我们总能组合出合适的区间）