线段树与树状数组
线段树（Segment Tree）与树状数组（Fenwick Tree / Binary Indexed Tree, BIT）是数组的「在线升级版」——它们在 O(log n) 时间内支持边改边查，把前缀和（只读查询 O(1)，但改一个元素要 O(n) 重建）与差分数组（区间改 O(1)，但查要 O(n) 还原）这两种「离线」结构，升级为「查询与修改交替进行」也能高效的「在线」结构。当题目出现「单点改 + 区间查」「区间改 + 区间查」且修改和查询交替到来时，朴素数组退化到 O(nq)，前缀和/差分也不够用，此时就要上线段树或树状数组。
两者本质都是用二叉树的分治结构把一个区间操作拆成 O(log n) 个树节点操作。线段树通用——每个节点存一个区间的聚合信息（和/最值/异或等），支持任意区间修改 + 区间查询，靠**懒标记（lazy propagation）**把区间修改摊到 O(log n)；**树状数组（BIT）**轻量——利用 lowbit（二进制最低位的 1）把前缀结构编码进一个普通数组，常数极小、代码极短，但只直接支持「单点改 + 前缀查」，区间查靠两前缀相减、区间改要上差分技巧。一句话选型：要区间改区间查 → 线段树；只要单点改前缀查且追求常数小 → 树状数组。
评价
优点
- O(log n) 在线维护区间信息：单点改、区间改、区间查（和/最值/异或）全是 O(log n)，让「查询与修改交替」不再退化——这是它们区别于前缀和/差分的核心价值。
- 线段树功能通用：每个节点存任意满足结合律的运算（和、积、min/max、GCD、异或），配合懒标记可实现区间批量修改，是区间问题的「瑞士军刀」。
- 树状数组常数极小：BIT 用一个普通数组 +
lowbit跳跃，无递归、无指针、缓存友好，实际运行比线段树快数倍，代码不到 20 行。
缺点
- 空间 O(n)（线段树需 4n）：线段树用数组存树要开
4n防越界；树状数组n+1即可——比前缀和的 O(n) 多了常数，但比平衡树轻。 - 代码与思维成本高：线段树的懒标记（
pushDown/pushUp）与边界处理极易写错；树状数组的lowbit含义抽象，初学难理解——是面试中区分度很高的考点。 - 只擅长区间聚合：两者维护的是「区间可合并」的信息（结合律），对「区间第 k 小」「区间众数」等不满足结合律的查询无能为力（需主席树/莫队等更重结构）。
本叶地图
- 入门 —— 前缀和的局限、为何需要在线结构、线段树（分治二叉树）与树状数组（lowbit 前缀结构）的定位、两者怎么选
- 线段树：区间查询与懒标记 —— 建树 O(n)、单点改/区间查 O(log n)、区间改 + 懒标记（lazy propagation）原理与实现
- 树状数组（BIT）：轻量的前缀结构 —— lowbit、tree[i] 管辖区间、单点改 + 前缀查 O(log n)、区间查 = 两前缀相减、与线段树对比
- 参考 —— API 速查、复杂度对比表、线段树/树状数组代码模板、选型决策、易错点