树状数组

总体功能上来说就是一个快速对区间进行求和和修改的数据结构，推荐文章里讲的真的很好，想要查的快多做缓存能到O(1)的效率，但是修改就会是O(n)的效率，那树状数组就是综合查找和修改的一个数据结构，能做到O(logn)的效率。
具体的算法细节就不再多赘述
是一个真的很好用的工具！

我专项的做了一些训练，出题的人还是挺厉害的，树状数组本身是求下标之间数量和的结构，但题目里的使用场景被扩充到了求某一些值之间的数量。

具体变换

求某些值之间的数量

题目：将元素分配到两个数组中 II

这个题目是一个模拟题，但是题目核心的复杂度在greaterCount函数的实现，如果直接遍历O(n)的复杂度，那么这个题目最大的复杂度就去到了O(n^2)，肯定是不够快的。

那有什么结构能够快速实现数组内大于等于某个数量的查询和插入呢？

答案：树状数组。

离散化
那要怎么做呢？将数组内的值作为横坐标，每个数据的纵坐标都是1，也就是创造了一个记录值数量的结构，那么对[1, 5]求和就能够表示:在原数组内值为1~5之间的总数，这就能够满足原问题了，但这会引入一个新的问题：

3 <= n <= 10^5
1 <= nums[i] <= 10^9

那就是树状数组的坐标会变得非常大，这时就有另外一个办法，我们将原数组进行一次离散化的压缩，例如：
100, 701, 504, 10201
可以被压缩成：1,3,2,4，其中需要记录1~100, 2~504, 3~701, 4~10201
它也可以被压缩成：1,2,3,4，其中1~100, 2~701, 3~504, 4~10201
这二者有什么差别吗？前者保留了映射数组的大小关系，但代价是一次O(nlogn)的排序，我们需要的当然是前者，但后者也是离散化。

>, >=, <和<=

题目：通过指令创建有序数组

树状数组很像是一个公式，它的公式本身只能求解<=值的数量，但是如何扩展到另外四个维度呢？

小于等于：原本公式化的Get(v)即可；
小于：原本公式化的Get(v-1)即可；
大于：当前总数 – Get(v)
大于等于：大于 + num[v]

置换

题目：统计数组中好三元组数目

原本的题目是比较复杂的，明显是需要遍历A数组，找到三个数(a,b,c)，然后在B数组中寻找a,b,c是否存在，且仍然保序。

置换是一个排列到另一个排列的双射。所有全排列的数组之间求前后顺序相关的题目都可以考虑这个方案。
置换即直接将AB数组做一个关于A数组的坐标映射：

A: [2,0,1,3], B: [0,1,2,3]
映射成：
A: [1,2,3,4], B: [2,3,1,4]

A: [4,0,1,3,2], B: [4,1,0,2,3]
映射成：
A: [1,2,3,4,5], B: [1,3,2,5,4]

因为做了置换，问题就从要在A, B中寻找一个三元数，变成了在B数组中找三个升序排列的子数组总共有多少个。
如何遍历呢？
三元数是(a, b, c)，只需要在B数组中遍历b就可以，然后在左边寻找有小于b的数量x，右边是否有大于b的数量y，sum(x * y)就是结果。
接下来的问题就是如何快速求解左边小于b, 右边大于b的数量呢？
依然是遍历，从左到右维护一个树状数组的结构，在遍历过程中就可以快速求解<x的数量，那如何求右边是否有>x的数量呢？因为是全排列，总共会有(n-x)个大于x的数量，那左边有l个的话，右边就有n-x-l个，综上。

额外的知识

离散化

离散化的方案其实很简单，就是排序之后做一个映射，但是可以直接对有序数组进行遍历，无需关心是否是完全连续，只需要保证离散化之后的坐标保留值本身的大小关系，代码如下：

sort(sortedNums.begin(), sortedNums.end());
unordered_map<int, int> indexMap;
for(int i = 0; i < sortedNums.size(); i++)
{
    indexMap[sortedNums[i]] = i + 1;
}

lower_bound

看到其他人的题解里用到了std::lower_bound，深入看了一下，参考文章。

除了lower_bound，标准库还包含upper_bound, equal_range和binary_search这4个查找函数，底层都是二分查找。

在那些同学的实现里，就是用这个替代前一小节的indexMap的映射关系。我的实现是用O(n)的时间建立了一个unordered_map，换取每次O(1)的读取。而他们的实现是不用O(n)的时间以及空间建立额外的哈斯表(unordered_map)或者红黑树(map)，直接用排序的数组进行二分查找。

这里C++标准库提供了四种查找：
lower_bound: 左到右查找第一个大于等于目标值的元素的迭代器
upper_bound: 左到右查找第一个大于目标值的元素的迭代器
equal_range: 从左到右找出等于目标值的迭代器范围, [first, last)
binary_search: 只返回是否存在，不返回迭代器

同时我还挺惊讶的，直接用lower_bound似乎比用unordered_map要更快？是因为反复扩充hash表吗？

vector::unique, vector::remove, vector::erase

这里是需要注意的！
vector::remove和vector::unique都对vector数组进行了改动，将待删除数组挪到了数组末尾，但并没有执行删除操作。可能是考虑到类似于栈的top和pop的读和删除的操作分离。

所以想要实际删除需要：

std::erase(std::unique(v.begin(), v.end()), v.end());
std::erase(std::remove(v.begin(), v.end(), val), v.end());

拆开的目的应该就是在删除之前还能保留一定读的能力。

本节参考：
https://blog.csdn.net/Vcrossover/article/details/106243627
https://cloud.tencent.com/developer/article/1022341
https://en.cppreference.com/w/cpp/algorithm/unique

End.

标签： 树状数组

树状数组学习笔记