前言
不愧是线段树，竟然卡我这么久，还是那句话：
十年OI一场空，不开long long见祖宗
#1 什么是线段树？
- 线段树长什么样？
通俗一点，线段树就是线段，树。
实际上，线段树是一棵完全二叉搜索树。
我们对于线段树模型的理解，在于它的每一个节点都维护了一定的线段区间，而该节点的两个儿子节点分别二分维护这个区间，就这样一直二分下去，直到整个序列被二分殆尽。
我们可以用简单的进制数学严格的证明线段树可以维护到所有区间。
- 线段树可以干什么？
刚才所说的维护，范围很广，可以求区间最值，求和，求乘积，除了在线性序列上的线段树，还有维护二维数组的矩阵树和三维数组的空间树
我们一般研究一维线段树。
- 误区？
ST表和线段树的区别：ST表不带修，线段树带修。
#2 如何建立一棵线段树。
首先，对于一棵完全二叉树，如果用一维数组来存的话，节点 \(k\) 的左子和右子就分别是 \(k*2\) 和 \(k*2+1\) ，我们改成位运算就是 \(k<<1\) 和 \(k<<1|1\)
所以，线段树的数组占空间很大，建议开 \(N\) 的四倍。
那么我们可以通过如下代码建立一棵维护区间和线段树：
int n;
long long a[100001];//原数组
long long t[100001<<2];//线段树数组
void pushup(int k){//这是更新父亲节点的函数
t[k]=(t[k<<1]+t[k<<1|1]);//很简单的加法
}
void build(int k,int l,int r){//k：线段树上节点编号，l、r：该节点表示的区间左右端点
if(l==r){//如果已经达到叶子节点
t[k]=a[l];//直接更新
}else{
int mid=l+((r-l)>>1);//区间中点
build(k<<1,l,mid);//建左子
build(k<<1|1,mid+1,r);//建右子
pushup(k);//更新父亲节点，这一步必须有
}
}