[OI 算法总结] 线段树

线段树是一种维护区间信息的数据结构，普遍时间复杂度一次操作的时间复杂度为 \(\mathcal{O}(\log n)\)。

例题 \(1\)：

给定一长为 \(n\) 的序列 \(a\)，初始时 \(a_i=0\)，现有 \(m\) 次操作，每次操作为以下两种之一：

1 pos val：将 \(a_{pos}\) 加上 \(val\);
2 l r: 求 \(\sum\limits_{i=l}^{r}a_i\).

发现可以使用树状数组。

这里介绍一下线段树的解法。

线段树本质上和树状数组差不多，都是通过维护一个区间的量的总和（或其他信息）来达到快速计算的目的。

例题 \(2\)：

给定一长为 \(n\) 的序列 \(a\)，初始时 \(a_i=0\)，现有 \(m\) 次操作，每次操作为以下两种之一：

1 l r val：将 \(a_i(l\le i\le r)\) 加上 \(val\);
2 l r: 求 \(\sum\limits_{i=l}^{r}a_i\)。

例题 \(3\)：

给定一长为 \(n\) 的序列 \(a\)，初始时 \(a_i\) 为给定的数，现有 \(m\) 次操作，每次操作为以下三种之一：

1 l r val：将 \(a_i(l\le i\le r)\) 加上 \(val\);
2 l r val：将 \(a_i(l\le i\le r)\) 乘上 \(val\);
3 l r val: 求 \(\sum\limits_{i=l}^{r}a_i\)。