线段树
线段树是一种用于高效区间修改与查询的二叉树结构，每个节点存储区间信息，通过递归建树、合并左右儿子信息实现维护。支持单点更新和区间查询，查询时若区间完全覆盖则直接返回，否则递归合并。扩展引入懒标记优化区间修改，延迟更新以保持复杂度为O(logN)，并给出维护区间最值及最大子段和的实现示例。
ST表&RMQ
发表于
更新于
本文字数：
200
阅读时长 ≈
1 分钟
ST表用于快速求区间最值（RMQ），设f[i][j]表示区间[i,i+2^j-1]最大值，预处理f[i][0]=a[i]，递推式为f[i][j]=max(f[i][j-1],f[i+2^(j-1)][j-1])。查询区间[l,r]时令k=log2(r-l+1)，答案为max(f[l][k],f[r-2^k+1][k])，代码使用二维数组预处理好后O(1)回答查询。
前缀和&二维前缀和
发表于
更新于
本文字数：
273
阅读时长 ≈
1 分钟
前缀和用于快速求区间和，一维前缀和简单；二维前缀和通过容斥原理定义f[i][j]为左上角到(i,j)的矩阵和，递推式为f[i][j]=a[i][j]+f[i-1][j]+f[i][j-1]-f[i-1][j-1]，查询(x1,y1)到(x2,y2)的和用f[x2][y2]-f[x1-1][y2]-f[x2][y1-1]+f[x1-1][y1-1]，代码中由随机数生成矩阵并多次查询异或答案。