> For the complete documentation index, see [llms.txt](https://anjia1.gitbook.io/ds-algo/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://anjia1.gitbook.io/ds-algo/advanced/tree-array.md).

# 5.2 树状数组和线段树（选学）

1. 树状数组：维护数组前缀和、区间和，是为了高效维护数组

2. 线段树：基于分治思想的二叉树，用于在区间上统计信息

3. 离散化：
   1. 场景：线段覆盖（批处理+无穷坐标）

4. [307. 区域和检索-数组可修改（M）](https://leetcode.cn/problems/range-sum-query-mutable/)：树状数组

5. [ACWing-243.一个简单的整数问题 2（H）](https://www.acwing.com/problem/content/description/244/)：线段树

6. [699. 掉落的方块（H）](https://leetcode.cn/problems/falling-squares/)：离散化

7. [327. 区间和的个数（H）](https://leetcode.cn/problems/count-of-range-sum/)：离散化+线段树