基本参照了 https://www.luogu.com.cn/blog/WannaDecrypt0r/shuo-ju-jie-gou-ru-men 的结构,内容是自己写的。
基本数据机构
1. 前缀和
长度为 $n$ 的 $a$ 数组的前缀和 $s$ 满足:
$$s_i=\sum_{j=1}^{i}a_j$$
这里的运算符可以不是加法,可以是任何运算符。
使用时预处理出前缀数组,查询前缀就直接输出,查询区间就两个前缀相减
2. 树状数组
码量较小的数据结构,用于解决一维动态问题,单点修改,区间查询。
可以查询半群信息(即满足“可减性”的 operator)。
https://www.luogu.com.cn/blog/Stitch0711/Binary-Index-Tree。
@sto_5k_orz 写的,十分高级,介绍了基本的 BIT,二维 BIT,$O(n)$ 建树,权值 BIT,区间 MEX 问题,树状数组合并,动态开点树状数组,树状数组维护不可差分信息,树状数组倍增,树状数组实现懒标记,可持久化树状数组。
树状数组码量小并且常数小,并且可以通过一些其他手段实现线段树、平衡树甚至主席树,并且树状数组并没有复杂度更劣,可以用于卡常。
3. 线段树
用于解决一维动态问题,区间修改,区间查询,常数较大。
这边注意一下 yxc 的写法常数巨大,因为结构体寻址的问题,拥有普通线段树两倍左右的常数。
思想是每个区间从 mid 拆开来变成两个区间,这样每个区间就可以表示为 $O(\log n)$ 个区间了。
更为详细的解释可见 线段树 1 的题解区。