[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\)。

[OI 算法总结] 线段树

原文：https://www.cnblogs.com/hhoppitree/p/14817421.html