ST 表基于倍增思想，用 st[i][j]st[i][j]st[i][j] 维护以 iii 为左端点、长度为 2j2^j2j 的区间 [i, i+2j−1][i,\,i+2^j-1][i,i+2j−1] 的最值，由两个长度为 2j−12^{j-1}2...

线段树用完全二叉树的数组存储，节点 p 的左右儿子为 p<<1 和 p<<1|1，开 4 倍空间。每个节点维护一个区间的信息，建树/修改/查询都在 O(log⁡n)O(\log n)O(logn) 的一条树链上完成。 单点...

树状数组基于二进制拆分，用 c[i]c[i]c[i] 维护以 iii 结尾、长度为 lowbit(i)lowbit(i)lowbit(i) 的区间 [i−lowbit(i)+1, i][i-lowbit(i)+1,\,i][i−lowbit(i)+1...

并查集用森林维护集合归属，f[x] 记 x 的父亲，根节点的父亲是自身。两种优化：路径压缩（查询时把路径上的点直接挂到根，常用）与启发式合并（小树并大树，带权并查集中常用）。 基本并查集（路径压缩） 1234567891011121314cons...

整数二分 情况一：左半段满足，右半段不满足 → 求最后一个满足的点 12345678910bool check(int x); // 判断 x 是否满足性质int solve_r(int l, int r) { // 找最后一个满足...