基础数据结构（前缀和/差分/树状数组/线段树）
前缀和与差分
多维前缀和
多维前缀和可以通过一维一维处理的方式，将复杂度控制在可控范围。
例如二维前缀和求法：
1. $sum_{i,j}=a_{i,j}$
2. $sum_{i,j}+=sum_{i-1,j}$
3. $sum_{i,j}+=sum_{i,j-1}$
数列上加多项式
给一个数列的一部分连续的数分别加上 $f(1),f(2),\dots,f(n),\dots$
key：任何一个最高次数为 $n$ 的多项式连续数列可以通过差分 $n+1$ 次表示。
因此，对于区间 $(l,r)$，我们先差分出一个从 $l$ 开始的 $f(1)$ 开始的数列，再差分出一个从 $r+1$ 开始的 $-f(r-l+2)$ 开始的数列抵消影响。
例题：NC225628 智乃酱的静态数组维护问题多项式。
树状数组与线段树
离线后树状数组
一些统计种类的问题可以通过这个方法来解决。
例如 [HEOI2012]采花
LazyTag
懒标记是线段树的核心之一。考虑需要维护的数值在懒标记下的运算很关键。
给出例题：
线段树
智乃酱的cube
带修改的 DP(DDP)
通过线段树可以完成一些能通过矩阵优化的 DP 的待修改版本。
智乃酱的双塔问题·极（带修改的DP，DDP）
智乃酱的双塔问题·改
势能线段树（带暴力成分的线段树）
有些数据具有单调性，就像势能不断下降至 0 势能点，观察并维护之可以让一些线段树结构看似有暴力修改，实则复杂度合法。
势能线段树模板题二
弩蚊怒夏
李超线段树
李超线段树是用来维护平面上的若干点的，用于快速找出在某一个 x 坐标，那一条的 y 值最大或最小。这在动态规划优化中也有作用。
模板：智乃的直线