浅谈用于区间求和的数据结构思路碎片
小柯
2020-02-08 14:51:35
## 前言
本文将涉及三种~~基础数据结构~~：
> 1.树状数组
> 2.线段树
> 3.分块
本文没有太大的逻辑联系，只是将一些思路碎片讲了讲。
### 注意:本文默认读者了解三个结构的基本实现！！！
$\texttt{------------------------}$华丽的分割线$\texttt{------------------------}$
# 树状数组
维护范围：满足区间可加性，并有逆运算的信息。
例如：和，异或和。
码长：较短。
效率：很高，$O(logn)$。
# 线段树
维护范围：满足区间可加性的信息。
例如：和，异或和，或和，最大子段和。
码长：较长。
效率：较高，$O(logn$*~~巨大常数~~$)$。
# 分块
维护范围：？？？。（本身就是优雅的暴力好不好？）
例如：和，异或和，或和，最大子段和，区间众数。
码长：较长。
效率：一般，$O(\sqrt{n}*$~~超大常数~~$)$。
$\texttt{------------------------}$华丽的分割线2$\texttt{------------------------}$
# 从分块说起
其实很早之前我就想过，既然对每个块的暴力加lazy，和边角的暴力加值都像是原来的暴力，那可不可以对每个块和块内的元素进行分块呢？
这个想法一直持续到我看到一片文章中这么说：
$\huge\texttt{"分块就是三层}\sqrt{n}\huge\texttt{叉树！！！"}$
~~本人亲自配图~~
这个应该很好理解吧？
此时，我的想法带进去就是增加这棵树的深度，以减少每个节点中的子节点数。
其实五层的话在$n=16$时就变成了中间的那个线段树的结构了。
先暂时抛开什么区间可加性，来研究一下~~珂学~~，不，是研究究竟怎么分最好。
$\texttt{设这棵树为}{k}\texttt{叉树，则每个节点都有}{k}\texttt{个子节点。}$
$\texttt{所以第}{1}\texttt{层共有}{k^0}\texttt{个}$
$\texttt{所以第}{2}\texttt{层共有}{k^1}\texttt{个}$
$\texttt{所以第}{n}\texttt{层共有}{k^2}\texttt{个}$
$\texttt{所以第}{n}\texttt{层共有}{k^3}\texttt{个}$
$\texttt{所以第}{m}\texttt{层共有}{k^m}\texttt{个}$
$\texttt{所以第共有}{k^0+k^1+k^2+....+k^m\approx k^{m+1} \approx k^m}$
$\texttt{故}{n=k^m,m=log^n_k}$
$\texttt{同线段树一样的做法，最后在这棵树上查询和修改操作的复杂度均为}$
$$O(k*log^n_k)$$
$\texttt{这明显是一个单谷函数（k>1时），所以用三分法求函数极值！！！}$
```cpp
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int n=1e6;
double l=1.001,r=1000,mid1,mid2;
double f(double x){
return x*log(n)/log(x);
}
int main(){
for(int i=1;i<=1000;i++){
mid1=l+(r-l)/3;
mid2=l+(r-l)*2/3;
if(f(mid1)-f(mid2)>1e-9)l=mid1;
else r=mid2;
}
printf("ans=%.3f\nf(2)=%.3f\nf(3)=%.3f\nf(ans)=%.3f\n",l,f(2),f(3),f(l));
return 0;
}
```
```cpp
ans=2.718
f(2)=39.863
f(3)=37.726
f(ans)=37.554
```
$\texttt{可见，在理论复杂度中，三叉树的效率最高。}$
$\texttt{------------------------}$华丽的分割线3$\texttt{------------------------}$
$\tiny\texttt{接下来要讲新东西了。}$
# 树状数组是线段树不可替代的
相信大家都知道权值线段树吧？其实树状数组也有类似用法。
权值线段树可以用于查询数的排名，但用排名查找数则有些艰难，不论二分还是倍增都是$O(log^2n)$的复杂度。
但树状数组就不同了，它被称为
$$\texttt{"天然的倍增"}$$
可以设计一个这样的算法：
> 1.初始化两个变量ans=0和sum=0。
> 2.从$logn$到$1$倒序考虑每个整数$p$
>>对于每个$p$，若$ans+2^p \le n$并且$sum+c_{ans+2^p}<k$，则令$ans=ans+2^p$，$sum=sum+c_{ans+2^p}$。
> 3.最后$ans+1$即为所求。
--来自李煜东《算法竞赛进阶指南》
但是权值线段树也有它的好处，就是它可以动态开点。
$\texttt{------------------------}$华丽的分割线4$\texttt{------------------------}$
# 关于树状数组的复杂度
树状数组的真实查询复杂度应该是$O(builtinPopcount(x))$
也就是二进制下为一的位的个数。
最坏情况下当然就是$logn$个啦。
还有一点就是：
树状数组的形状像不像对数函数？
（不信你再看看前面我画的画）
而查询某个点的复杂度恰好就是这个点的高度。
而整棵树的平均高度为$logn/2$，所以期望复杂度为$O(logn)$。