浅谈用于区间求和的数据结构思路碎片

· · 个人记录

前言

本文将涉及三种基础数据结构：

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时），所以用三分法求函数极值！！！} 
#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;
}
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)。