前缀和、差分、离散化 参考资料： 前缀和 & 差分 - OI Wiki 离散化 - OI Wiki 前缀和 数列前 \(n\) 项的和，是一种重要的预处理方式。 一维前缀和 可得到其递推式\(S_0=0,S_i = S_{i-1}+a_i\) 作一维前缀和数组 \(ps\)，其中下标i表示前 \(i\) 项的和 对区间[l,r]求和，显然用 \(ps[r]-ps[l-1]\) 即可，时间复杂度为 \(O(1)\) 二维/多维前缀和 将一维前缀和扩展到多维的情形。其常见的求解方法有两种 基于容斥原理 多用于二维前缀和的情形。给定大小为 \(m\times n\) 的二维数组 \(A\) ，要求求出其前缀和 \(S\)。那么，\(S\) 同样是大小为 \(m\times n\) 的二维数组，且 \[S_{i,j} = \sum\limits_{i'\leq{i} }\sum\limits_{j'\leq{j}}A_{i'j'}\] 显然，对于 \(S_{i,j}\)，我们可以通过容斥原理获得: \[S_ ...

归并排序 定义 归并排序（merge sort）是高效的基于比较的稳定排序算法 性质 归并排序基于分治思想将数组分段排序后合并，时间复杂度在最优、最坏与平均情况下均为 \(O(nlogn)\)，空间复杂度为 \(O(n)\)。 归并排序可以只使用 \(O(1)\) 的辅助空间，但为便捷通常使用与原数组等长的辅助数组。 过程 合并 归并排序最核心的部分是 合并（merge）过程：将两个有序的数组 \(a[i]\) 和 \(b[i]\) 合并为一个有序数组 \(c[k]\)。 从左往右枚举 \(a[i]\) 和 \(b[j]\)，找出最小的值并放入数组 \(c[k]\)；重复上述过程直到 \(a[i]\) 和 \(b[j]\) 有一个为空时，将另一个数组剩下的元素放入 \(c[k]\) 。 为保证排序的稳定性，前段首元素小于或等于后端首元素时（\(a[i]\leq b[j]\)）而非小于时（\(a<b\)），就要作为最小值放入 \(c[k]\) 数组实现： 12345678910111213141516void merge(const int *a, i ...

参考资料：倍增 - OI Wiki 倍增 定义 倍增法（binary lifting），即“成倍增长”的含义。我们在进行递推时，如果状态空间很大，那么通常的线性递推无法满足空间和时间复杂度的要求。那么，我们可以通过成倍增长的方式，只递推状态空间中在 \(k\) 的整数次幂位置上的值作为代表。当需要其他位置上的值时，我们通过k的一元多项式之和得到。所以使用倍增算法也要求我们递推的问题的状态空间关于 \(k\) 的次幂具有可划分性。通常情况下 \(k\) 取 \(2\) （这样每项的系数要么为 \(1\) ，要么为 \(0\) ） 应用 RMQ问题 RMQ 是 Range Maximum/Minimum Query 的缩写，表示区间最大（最小）值 。使用 ST表 是基于倍增思想的 RMQ问题 求解方式 树上倍增求LCA 求最近公共祖先的倍增解决方式