这是灵茶山艾府的算法题单的学习笔记，将介绍前缀和/栈/队列/堆/字典树/并查集/树状数组/线段树等经典数据结构。

枚举

双变量问题，通过枚举转化为单变量。需要注意枚举同时维护答案。

对于三变量以上，可以考虑枚举中间值。

前缀和

一维情况，对于数组 arr[n] ，要求区间 [i, j] 内所有元素的和，可以考虑令 sum[i+1] = sum[i] + arr[i] 则区间和为： sum[j+1]-sum[i] ，注意初始化 sum[0] = 0 。

二维前缀和

考虑使用 sum[i+1][j+1] 表示左上角矩阵元素和，即从(0,0)到(i, j)。则有递推关系：
$$
sum[i+1][j+1] = sum[i][j+1] + sum[i+1][j] - sum[i][j] + arr[i][j]
$$
可以画图理解减去 $sum[i][j]$ ，因为这部分算了两次。

相对应的，当我们需要求某个矩形区间和时，对 sum 数组也需要使用类似的操作：
$$
sum((i, j), (x, y)) = sum[x+1][y+1] - sum[x+1][j] - sum[i][y+1] + sum[i][j]
$$
这个公式表示点 $(i, j)$ (左上角) 到点 $(x, y)$ (右下角) 矩形内元素之和，同样需要画图以更直观地理解。

栈

差分数组

高效进行区间加和操作的数据结构。

差分数组关键词是还原，也就是说，对差分数组求和，可以方便地求出原数组。

例如，当我们希望对数组从 i 到 j 每个元素加1，若使用遍历，那么时间复杂度会是 $O(n)$ 。

此时，我们引入一个差分数组 diff[i] ，只要让 diff[i]=1 以及 diff[j+1]=-1 就可以用 $O(1)$ 的复杂度解决。注意：结尾是j+1而不是j。

想象差分数组就是“地势抬高器”，它可以使 $i$ 之后的所有地面上升。同理，也可以使 $i$ 之后的所有地面下降，当然，需要注意这个操作是叠加的。