线段树

线段树是一种高级数据结构，我自己刷题用这种数据结构已经很多次了，可是一旦过段时间不刷就容易忘记这个结构，因此这里做下笔记，忘记的时候方便自己回忆。

1.基础结构

线段树基础信息 OI 官网介绍：线段树介绍_OI

简单来说，线段树可以在的时间内批量修改和查询区间的值，但批量操作需要有合并性，比如批量相加，乘除，最大最小值等。其空间复杂度为，准确来说是，4 这个数字取自实践尝试所得。OI 官网中的写法是使用静态数组提前开辟所有节点，而我更喜欢动态开节点的做法，动态开点在的区间范围内进行少量操作时不会爆空间：

class SegmentTreeNode {
  int start, end, mid;
  int maxval, minval;
  int lazyadd = 0;
  SegmentTreeNode left, right;

  SegmentTreeNode(int start, int end) {
    this.start = start;
    this.end = end;
    this.mid = (start + end) >> 1;
    this.maxval = this.minval = 0;
    this.left = null;
    this.right = null;
  }
}

class SegmentTree {
  SegmentTreeNode root;

  SegmentTree(int start, int end) {
    root = new SegmentTreeNode(start, end);
  }

  private void pushdown(SegmentTreeNode root) {
    if (root.left == null) {
      root.left = new SegmentTreeNode(root.start, root.mid);
    }
    if (root.right == null) {
      root.right = new SegmentTreeNode(root.mid + 1, root.end);
    }
    if (root.lazyadd != 0) {
      root.left.maxval += root.lazyadd;
      root.left.minval += root.lazyadd;
      root.right.maxval += root.lazyadd;
      root.right.minval += root.lazyadd;
      // 懒标记也必须遵循累加
      root.left.lazyadd += root.lazyadd;
      root.right.lazyadd += root.lazyadd;
      root.lazyadd = 0;
    }
  }

  private void pushup(SegmentTreeNode root) {
    root.maxval = Math.max(root.left.maxval, root.right.maxval);
    root.minval = Math.min(root.left.minval, root.right.minval);
  }

  private void modify(SegmentTreeNode root, int start, int end, int addval) {
    if (root.start >= start && root.end <= end) {
      root.maxval += addval;
      root.minval += addval;
      root.lazyadd += addval;
      return;
    }
    pushdown(root);
    if (root.mid >= start) {
      modify(root.left, start, end, addval);
    }
    if (root.mid < end) {
      modify(root.right, start, end, addval);
    }
    pushup(root);
  }

  private int[] findMaxNMin(SegmentTreeNode root, int start, int end) {
    if (root.start >= start && root.end <= end) {
      return new int[] { root.maxval, root.minval };
    }
    pushdown(root);
    int maxval = -1, minval = (int) 1e9;
    if (root.mid >= start) {
      int[] larr = findMaxNMin(root.left, start, end);
      maxval = Math.max(maxval, larr[0]);
      minval = Math.min(minval, larr[1]);
    }
    if (root.mid < end) {
      int[] rarr = findMaxNMin(root.right, start, end);
      maxval = Math.max(maxval, rarr[0]);
      minval = Math.min(minval, rarr[1]);
    }

    return new int[] { maxval, minval };
  }


  public void modify(int start, int end, int addval) {
    modify(root, start, end, addval);
  }

  public int[] findMaxNMin(int start, int end) {
    return findMaxNMin(root, start, end);
  }

}

这里解释一下什么场景需要使用懒标记，什么场景不需要。懒标记要怎么修改，为什么要怎么修改。

2.高阶用法

2.1 扫描线

2.2 介值定理查找元素