线段树

前置知识

数组，结构体，二叉树

引入

有时候我们会遇到一些大规模的区间查找和区间修改问题，比如让你维护一个 $10^5$ 长度的数列，要求操作有区间求和、区间加（区间每个数加上一个值），让你在一秒内完成 $10^5$ 次操作。
暴力是肯定不行的，数据范围太大，会超时。
所以我们就有一种专门解决大范围区间修改查询的数据结构：线段树。

线段树

线段树本质上是把整个数列拆分了，用一个一个区间来表示。
比如有 $n$个节点
根节点代表整个数列的区间$[1,n]$，
根节点的两个子节点代表根区间二分成两部分，也就是 $[1,\operatorname{mid}]$ 和 $[\operatorname{mid},n]$。
而子节点也是一棵线段树。
一直往下眼神，叶子结点就代表着单一位置$[a,a]$