树状数组（Binary Index Tree, BIT）支持单点修改和区间查询，时间复杂度为 $O( ext{log} n)$。其实现简单且速度快，适合处理动态数据。通过二进制表示，树状数组将节点数压缩到与数组长度相同。修改和查询操作通过计算 $ ext{lowbit}(x)$ 实现，能有效更新和查询前缀和。构建树状数组可通过预处理前缀和数组，时间复杂度为 $O(n)$。

动态开点线段树用于维护大数组，按需创建节点以节省空间，支持区间求和和单点修改。可持久化线段树存储历史版本，避免重复构建。权值线段树处理区间内数的出现次数，适用于第K小值查询。