简单线段树/树状数组练习题小全

## 题目说明 保证大部分题目主要实现部分是线段树，剔除了仅使用线段树优化的题目。 本题单内的题目会不定期更新。 ### 必须掌握的模板 - P3372：线段树模板。 - P3374：单点修改，区间查询 - P3368：区间修改，单点查询 ### 较为复杂的懒标记维护 - P3373：要搞清楚加标记和乘标记之间的联系 - P1253：推平时要清空加法标记 ### 一些练手题 写好线段树的关键在于不断地练习，建议不要复制板子修改提交。 - P1816：区间查询最小值。 - P1438：线段树维护差分数组，区间修改，区间查询。 - P2023：P3373 的双倍经验。 ### 权值线段树、离散化与动态开点 这些都是很经典而且很板的 trick，务必掌握。 - P1908：权值线段树求解逆序对问题。 - P1801：在权值线段树上处理询问。 - P1637：同时处理顺序对与逆序对信息。 - P1168：在权值线段树上根据排名分治。 - P1486：批量加减可以在外部维护一个懒标记，然后就是权值线段树的问题了。 - CF915E：动态开点线段树的典题。 ### 特殊条件下线段树时空复杂度的证明 考察对信息中的性质的观察、分析与应用。 - P7492：对每个点的有效或操作至多只有 31 次。 - P4145：对每个点的有效开方下取整操作不超过 10 次。 - CF1638E：线段树维护区间连续颜色段+推平是均摊 $O(n\log{n})$ 的。 ### 询问/修改的巧妙转化 - CF242E：拆位处理区间异或/区间和，有 32 倍常数。 - P4513：线段树维护区间最大子段和——借助线段树的分治结构，以分治做法求解。 - P5278：考虑一个有限项数列是等差数列的充要条件，分别维护相关信息。 - P6617 减少无用的前驱后继维护。 - P10463：在差分数组上可以同时支持查区间 $\gcd$，做区间加。 ### 推式子拆贡献 形式多样，考察数学推导能力。 - P1471：拆式子维护计算方差的信息。 - P6327：利用三角函数公式处理区间加，并维护区间 $\sin$ 和。 - P2221：通过推导并维护每个收费站的贡献来算期望。 - P3707：暴力拆解 $\sum$。 ### 普通的线段树离线询问 典型的例子：询问区间包含的不同颜色种类，通常上可持久化能做到在线。 - P1972 - CF1000F ### 一些杂题 - P4514：二维树状数组。 - P1937：贪心+线段树 - P2572：码农练习题。 - P10673 - SP2916 ### 0/1 类线段树 用 0/1 类线段树可以很好地解决一些特定问题。 - CF1539F：从小到大离线算每个数的值。 - P2824：二分答案，将大小关系转化为 0/1 来 check。 ### 线段树维护矩阵乘法 - P6864：线性变换转成矩阵乘法，以支持快速维护修改。 - P8868：线段树+矩阵维护区间历史和