概念

基本结构以及建树

image.png
这样的一棵树应该是这样的：
image.png
我们使用一个数组对树形数据进行存储，因此可以注意到一个关键点，根节点与叶子节点的下标关系（注意这个方便的计算规律来自下标从1开始）：
image.png

  1. struct SegmentTree<T> {
  2.     inner: Vec<T>,
  3.     data: Vec<T>
  4. }
  6. impl<T> Debug for SegmentTree<T>
  7.     where T: Debug
  8. {
  9.     fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
  10.         f.write_fmt(format_args!("从原数组{:?}\n获取到的线段树结果为：{:?}",
  11.                                  self.data, self.inner))
  12.     }
  13. }
  15. impl<T> SegmentTree<T>
  16.     where T : Copy + Ord + PartialEq + Default + Add<Output=T>
  17. {
  18.     pub fn new(data: Vec<T>) -> SegmentTree<T> {
  19.         Self {
  20.             // 这个初始化的数组的大小足够应付10^5个数据
  21.             inner: vec![T::default(); data.len() * 3],
  22.             data
  23.         }
  24.     }
  26.     pub fn build(&mut self) {
  27.         if self.data.len() == 0 { return; }
  28.         self.build_section(0, self.data.len()-1, 1);
  29.     }
  31.     /// 线段树建树,对 [s..t] 区间建立线段树,当前根的编号为 p
  32.     pub fn build_section(&mut self, s: usize, t: usize, p: usize) {
  33.         if self.data.len() == 0 { return; }
  34.         // 递归结束条件，根节点时，节点值为原值
  35.         if s == t { self.inner[p] = self.data[s]; }
  36.         else {
  37.             let mid = s + ((t - s) >> 1);
  38.             // 后序遍历
  39.             self.build_section(s, mid, p*2);
  40.             self.build_section(mid+1, t, p*2+1);
  41.             // 每个节点的值为左右节点值之和
  42.             self.inner[p] = self.inner[p*2] + self.inner[p*2+1];
  43.         }
  44.     }
  45. }

区间修改

参考资料知乎
如果要求修改区间 [l..=r]，把所有包含在区间 [l..=r]中的节点都遍历一次、修改一次，时间复杂度无法承受。我们这里要引入一个叫做 「懒惰标记」 的东西。
懒标记是线段树的精髓所在。对于区间修改，朴素的想法是用递归的方式一层层修改（类似于线段树的建立），但这样的时间复杂度比较高。使用懒标记后，对于那些正好是线段树节点的区间，我们不继续递归下去，而是打上一个标记，将来要用到它的子区间的时候，再向下传递。
image.png
image.png
image.png
在具体编写代码的时候存在三种情况，先放一个完整的图在这里，注意我们使用线段树是为了区间查询，因此需要有节点与对应区间进行匹配的过程：
image.png

image.png
第二步是剪枝的关键，当我们找到一个完全在目标区间内的区间的时候，才是打上懒标记，然后节省继续往下递归的开销：image.png
第三步比较麻烦，需要拆解区间
image.png
image.png
这样就可以看代码了：

  1. pub fn query(&mut self, l: usize, r: usize) -> i32 {
  2.     self.query_section(l, r, 1, 1, self.data.len())
  3. }
  4. /// 区间查询的实现，[l..=r] 区间查询和，[cl..=cr]为当前区间，p为此时根节点
  5. pub fn query_section(&mut self, l: usize, r: usize, p: usize, cl: usize, cr: usize) -> i32 {
  6.     return if cl > r || cr < l { 0 }
  8.     else if cl >= l && cr <= r {
  9.         self.inner[p]
  10.     } else {
  11.         let mid = cl + ((cr - cl) >> 1);
  12.         self.push_down(p, (cr - cl + 1) as i32);
  13.         self.query_section(l, r, p * 2, cl, mid)
  14.             + self.query_section(l, r, p * 2 + 1, mid + 1, cr)
  15.     }
  16. }
  18. pub fn update(&mut self, l: usize, r: usize, d: i32) {
  19.     self.update_section(l, r, 1, d, 1, self.data.len());
  20. }
  22. /// 区间更新的实现，[l..=r] 区间中更新加上值 d，[cl..=cr]为当前区间，p为此时根节点
  23. pub fn update_section(&mut self, l: usize, r: usize, p: usize, d: i32, cl: usize, cr: usize) {
  24.     // 剪枝，如果当前区间与更新区间无交集
  25.     if cl>r || cr<l { return; }
  26.     else if cl >= l && cr <= r {
  27.         // 第二种情况，当前区间在更新区间内部，我们不继续往下,而是将此最大区间进行更新，并使用懒标记
  28.         // 因为是一整个区间都加上了d，因此这里需要的是乘以区间长度
  29.         self.inner[p] += (cr - cl + 1) as i32 * d;
  30.         // 注意，非叶子节点才进行懒标记，而且只是标记d，也即区间中每个元素的更新值
  31.         if cr > cl {
  32.             self.marker[p] += d;
  33.         }
  34.     }else {
  35.         // 两个区间相交但不包含,这时把当前区间一分为二，分别进行处理。
  36.         // 如果存在懒标记，要先把懒标记传递给子节点
  37.         let mid = cl + ((cr - cl) >> 1);
  38.         // 懒标记传递给子节点
  39.         self.push_down(p, (cr - cl + 1) as i32);
  40.         self.update_section(l, r, p*2, d, cl, mid);
  41.         self.update_section(l, r, p*2+1, d , mid+1, cr);
  42.         // 因为是传递下去到最大区间，那么回溯的时候需要根据子节点更新当前节点的值
  43.         self.inner[p] = self.inner[p*2] + self.inner[p*2+1];
  44.     }
  45. }
  46. /// 标记往下传递一层
  47. fn push_down(&mut self, p: usize, len: i32) {
  48.     // 懒标记传递给子节点,就一层
  49.     self.marker[p*2] += self.marker[p];
  50.     self.marker[p*2+1] += self.marker[p];
  51.     // 同时更新子节点的值，需要考虑区间长度，因为我们标记记录的是d，但是区间更新
  52.     // 需要考虑多个d
  53.     self.inner[p*2] += self.marker[p] * (len - len/2);
  54.     self.inner[p*2+1] += self.marker[p] * (len / 2);
  55.     self.marker[p] = 0;
  56. }

测试代码：

#[test]
fn test_update_query() {
    let mut tree = SegmentTree::new(vec![1,2,3,4,5]);
    tree.build();
    println!("新建树为：\n{:?}", tree);
    let i = tree.query(1, 4);
    println!("{}", i);

    tree.update(1, 4, 1);
    println!("{:?}", tree);

    let i = tree.query(1, 4);
    println!("{}", i);
}

动态开点的线段树

933. 最近的请求次数

三叶的题解中提到了这种做法，但是不太看得懂