线段树
原理
线段树，就是把一段区间，不断二分，分为一颗二叉树，去维护区间信息。
算法结构
一个完整的线段树代码中，通常由六个部分组成
这里展示以一个简单的整数问题2为例
struct Node
节点部分，其中维护的是，关于线段树所有需要用到的信息。
这里需要着重说一下的是，一般我们的Node会开到四倍区间大小
左右端点 ,题目中会用到的信息 及懒标记
例子(或者叫板子？emm)
struct Node
{
int l,r;
LL sum; //(区间需要维护的值)
LL add;//（懒标记，可以有多个）
}tr[N*4];
pushup
这个函数的作用是将子节点产生的变化，传递到父节点。
所以一般在的位置都是在已经递归结束的函数后，因为此时子节点的变化已经结束，可以去更新父节点了
只有这个地方会使用，一定记住,因为如果每次发生变化，就立即进行回溯改变，就破坏了懒标记的作用。
懒标记便是为了延迟更新，当要改变的区间完全包括某个树中区间时，直接将这个区间的懒标记+d即可，不用进行pushup操作，等到，查询时需要这个区间时，我们再进行pushdown操作，将影响传递到它的子节点，在一步步回溯回来时，再利用pushup去更新，父节点！！！
很关键，易错点。
防止错误，首先需要死记住，pushup和pushdown的位置。然后再进行理解。
void pushup(int u)
{
tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
}
pushdown
这个函数的作用是将父节点产生的变化，传递到子节点
但这里一定要提及一下，它所在的位置是需要进行分裂时，之前。
例如：查询时，遇到的树中区间与我所查的区间是有一部分相交的情况，此时就要分裂了，因此要pushdown
另外，再进行区间改变时，当所要改变的区间与树中区间是有一部分相交时，此时也要分裂，pushdown一下。
void pushdown(int u)
{
Node &root = tr[u],&left = tr[u<<1],&right = tr[u<<1|1];
if(root.add){
left.add+=root.add,left.sum+=(LL)(left.r-left.l+1)*root.add;
right.add+=root.add,right.sum+=(LL)(right.r-right.l+1)*root.add;
root.add=0;//传递到到下边后，要清空。
}
}
build
build函数的操作，比较简单，就是不断二分，向下递归，递归到区间内只剩下一个数字了，则停止进行赋值，然后回溯。
这里可以注意看pushup的位置
void build(int u,int l,int r)
{
if(l==r) tr[u]={l,r,w[r],0};
else
{
tr[u]={l,r};//这一步比较容易忘记
int mid = l + r >> 1;
build(u<<1,l,mid),build(u<<1|1,mid+1,r);
pushup(u);
}
}
modify
modify函数，在改变时，分为单点修改和区间修改。单点修改比较简单，只要查到需要改的数字下标，改了之后pushup即可，这里不说了。这里着重提一下区间修改。
要分为三种情况
-
所要改变区间包含树中的区间，则直接将需要加或者减的数，直接更改到该树中区间的懒标记上，同时改变需要改变的值
-
所要改变区间与树中区间交叉一部分，mid=tr[u].r+tr[u].l>>1，则判断若要改变区间l是否比mid小,若是，则递归到左边界，再判断所改变区间的r是否>mid,若是，则递归到有边界。
-
第三种情况不可能出现，但是还是提一下。所要改变区间被，树中区间所包含。
其中第一种情况，因为区间没有分裂情况，所以不用pushdown。而第二种，有分裂情况出现，则需要pushdown一下，再进行接下来的操作。
void modify(int u,int l,int r,int d)
{
if(tr[u].l>=l&&tr[u].r<=r)
{
tr[u].sum+=(LL)(tr[u].r-tr[u].l+1)*d;
tr[u].add+=d;
}
else
{
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if(l<=mid) modify(u<<1,l,r,d);
if(r>mid) modify(u<<1|1,l,r,d);
pushup(u);
}
}
query
query函数，跟modify函数几乎相同，只要注意分裂之前要用pushdown即可
LL query(int u,int l,int r)
{
if(tr[u].l>=l&&tr[u].r<=r) return tr[u].sum;
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
LL sum = 0;
if(l<=mid) sum += query(u<<1,l,r);
if(r>mid) sum += query(u<<1|1,l,r);
return sum;
}
以上就是，以一道题目为例，说明了一下线段树的结构
能解决的问题
- 区间修改
- 区间查询
- 单点修改
- 单点查询
一些例题
比较经典，如何去维护一个区间的最大公约数，利用差分数组。因为
\[ gcd(a_1,a_2,...,a_i)=gcd(a_1,a_2-a_1,...,a_i-a_{i-1}) \]懒标记的复杂运用，同时维护两个懒标记，使区间可以进行乘和加。
我们在维护pushdown时，利用的是先乘后加的操作
举个例子，例如，新加进来的add',mul'
\[sum=sum*mul'+(r-l+1)*add' \] \[mul=mul*mul' \] \[add=nul'*add+add' \]则pushdown中更新，左右节点的eval函数
void eval(Node &u,LL add,LL mul)
{
u.sum=(u.sum*mul+(u.r-u.l+1)*add)%p;
u.mul=mul*u.mul%p;
u.add=(u.add*mul+add)%p;
}
展示了，可能我们需要维护许多的信息。
其实还有一个，扫描线，但是它有些特殊，我们放到别的地方单独记忆。