作用

解决单点修改、区间询问（区间修改、单点询问，区间修改、区间询问）的问题

复杂度

$O(nlogn)$

概念

线段是是一颗二叉树，线段树上的每一个节点对应序列的一段区间，根节点对应的是[0,n-1]。若一个节点对应的是[l,r]时，当l=r的时候，他是一个叶节点，没有左右儿子，否则它一定有2个儿子，令mid = (l+r)/2;那么，左儿子对应的区间为[l,mid],右儿子对应的区间是[mid+1,r].
·线段树最后一层有n个节点，那么整个线段树的节点数为2n-1(自证不难)。 ·线段树的高度为$log_2N$层，当我们需要维护的序列长度是2的整数次幂的时候，线段树是一颗满二叉树。其他情况下，n-1层是满二叉树，最后一层可能不满。

注意，线段树的数组不能只开到2n，要开到4n

代码

见板子

区间查询操作

三种情况

1. 当前区间与带询问区间完全无交集，返回一个对答案无影响的值，如极大的数或者极其小的数
2. 询问区间完全包含当前区间，直接返回所维护区间的最小值
3. 除了上面两者情况，对两个子节点递归处理，返回最小/最大值 代码见板子

延迟标记

1.区间修改，单点查询 只要记录一下修改对结果的影响就可以，代码见板子