一直没碰过线段树，个人认为好长好难，不过这几天做题遇到了裸的线段树的题，TAT。
线段树我理解就是把二叉树的左右节点现在分别看成是两个区间。
那么现在这两个区间的端点怎么存放？怎么能够把这个区间里的数（一般指的就是在这个区间的数值的和）存放起来呢？
比较传统化的是用一个结构体来存放。比如：
代码语言：javascript复制struct node
{
int l, r; // l,r分别是左右端点
int w; // 用来存放这个区间的值（和）
};这样就可以解决了数值的存放问题了。
学习建立二叉树的时候是用指针、结构体来建立的，依靠指针来找子节点或者根节点，当然在线段树中依然可以那么建立，不过
在使用时可能会因为指针的特点，RE之类的错误经常出现，于是就是就有人想到用结构体类型数组来模拟建立。
这个结构体需要开多么大才合适呢？
一般需要开4倍空间才可以。（当时自我感觉认为3倍就够了，但是RE了一次，可以在纸上手动画一下，帮助理解）
线段树一般就是来解决比较直观的问题（当然也有好多神级题目来考你的线段树,这里暂时忽略一下），比如给你一个N长度的一
组数，再给你L、R。这样就可以问你：任意L~R之间的数的和（这就是所谓区间查询，当L==R时，就变成了单点查询）。
如果仅仅是查询那么前缀和就可以做了，如果数据N不大，直接暴力就好了。
现在再加一个操作，给你L、R、X，每次在L~R区间上加上X（这就是区间修改，当L==R时，就是单点修改），这个操作后再查
询，这两个操作的次数非常多，一般都会TLE了。
这样的问题就可以用线段树来解决了。
首先是建一颗线段树：
代码语言：javascript复制void BuildSegmentTree(int k, int l, int r)
{
tree[k].l = l; // 存放左右端点
tree[k].r = r;
if(l == r) // 如果是l==r时，就是到了线段树的最下层，也就是叶子，存放数本身的值。
{
scanf("%lld", &tree[k].w);
return ; // ！！！
}
int m = (tree[k].l tree[k].r) >> 1; // m = (tree[k].l tree[k].r) / 2;
BuildSegmentTree(k << 1, l, m);
BuildSegmentTree(k << 1 | 1, m 1, r);
tree[k].w = tree[k << 1].w tree[k << 1 | 1].w; // tree[k << 1 | 1].w 相当于 tree[k * 2 1].w
}建树的过程比较简单，就是递归建树就可以了。
<以下操作的英文名字纯属为了避免混淆了，根据自己喜欢命名即可>
1、单点修改（Single point modification）
代码语言：javascript复制void Single_Point_Modification(int k, int x, int y) // x是待修改的点，y是添加的值
{
if(tree[k].l == tree[k].r) // 如果是叶子，也就找到了单个点
{
tree[k].w = y;
return ;
}
int m = (tree[k].l tree[k].r) >> 1;
if(x <= m) Single_Point_Modification(k << 1,x, y); //如果待修改值x小于中间值，递归左边
else Single_Point_Modification(k << 1 | 1, x, y); //如果待修改值x小于中间值，递归左边
tree[k].w = tree[k << 1].w tree[k << 1 | 1]. w; //别忘了因为修改这个值，所以需要更新它的上一层的值
}2、单点查询（Single point query）
代码语言：javascript复制void Single_Point_Query(int k, int x) // 单点查询比较好理解，如果查到了直接返回就好了，所以函数可以写成int类型
{
if(tree[k].l == tree[k].r) // x为需要查询的点
{
ans = tree[k].w;
return ;
}
int m = (tree[k].l tree[k].r) >> 1;
if(x <= m) Single_Point_Query(k << 1, x);
else Single_Point_Query(k << 1 | 1, x);
}3、区间查询（Interval query）
代码语言：javascript复制void Interval_Query(int k, int x, int y) //查询区间x~y
{
if(tree[k].l >= x && tree[k].r <= y) // 如果查询的区间在这个范围内，直接加上
{
ans = tree[k].w;
return ;
}
int m = (tree[k].l tree[k].r) / 2; // 继续递归查询
if(x <= m) Interval_Query(k << 1, x, y);
if(y > m) Interval_Query(k << 1 | 1, x, y);
}4、区间修改（Interval modification）
在区间修改时会遇到一些问题，如果每次修改都是查询到叶子所在的点来修改，再返回到上一层，依次完成更新，如果是这种操作理论上时间复杂度就是比较高了，如果是查询、修改、查询……这样可能就要QAQ了。可以换一种想法，只有需要查询到修改过的这个区间时，我们才把修改过的这个区间的值算一下，如果没有查询到这个区间，那么这个修改的值就一直存在上一层不动（相当于它的父节点就可以了，如果查询到了，根据这个区间的数的个数把每个数都加上就可以，然后把在父节点的这个标记更新清零），因为用到才会更新的原因吧，所以这个标记就被称作是懒标记了。
如果需要进行区间修改那么结构体中就要多一个变量，来存放需要的那个懒标记。
代码语言：javascript复制struct node
{
int l, r; // l,r分别是左右端点
int w; // 用来存放这个区间的值（和）
int f; // 懒标记
};现在知道了这种思想，那么如果实现的话，首先是这个标记怎么把它传下去呢？
只要是修改的区间包括了k这个点，就需要把懒标记下传下去，然后更新w值，再把标记清零。
代码语言：javascript复制void down(int k)
{
tree[k << 1].f = tree[k].f; // 子节点都要加上标记
tree[k << 1 | 1].f = tree[k].f;
tree[k << 1]. w = tree[k].f * (tree[k << 1].r - tree[k << 1].l 1); // 数值更新
tree[k << 1 |1].w = tree[k].f * (tree[k << 1| 1].r - tree[k << 1| 1].l 1);
tree[k].f = 0; // “父节点”（懒标记）清零
}区间修改：
代码语言：javascript复制void Interval_modification(int k, int x, int y,int z) // [x,y]区间上每个值都加上z
{
if(tree[k].l >= x && tree[k].r <= y) //如果全部在这个区间内，那么这个区间的总个数*z的值加在父节点上即可
{
tree[k].w = (tree[k].r - tree[k].l 1) * z;
tree[k].f = z; // 把标记存在这个地方，如果还可以继续往下访问，利用down来解决
return;
}
if(tree[k].f) down(k); //懒标记下传。
int m = (tree[k].l tree[k].r) >> 1;
if(x <= m) Interval_modification(k << 1, x, y, z);
if(y > m) Interval_modification(k << 1 | 1, x, y, z);
tree[k].w = tree[k << 1].w tree[k << 1 | 1].w; // 存放更新后的值
}当然不喜欢这么多函数，就把懒标记下传写到这里面去就可以了。
合并以后：
代码语言：javascript复制void Interval_modification(int k, int x, int y,int z) // [x,y]区间上每个值都加上z
{
if(tree[k].l >= x && tree[k].r <= y)// 如果全部在这个区间内，那么这个区间的总个数*z的值加在父节点上即可
{
tree[k].w = (tree[k].r - tree[k].l 1) * z;
tree[k].f = z; // 把标记存在这个地方，如果还可以继续往下访问，利用down来解决
return;
}
if(tree[k].f) //懒标记下传。
{
tree[k << 1].f = tree[k].f; // 子节点都要加上标记
tree[k << 1 | 1].f = tree[k].f;
tree[k << 1]. w = tree[k].f * (tree[k << 1].r - tree[k << 1].l 1); // 数值更新
tree[k << 1 |1].w = tree[k].f * (tree[k << 1| 1].r - tree[k << 1| 1].l 1);
tree[k].f = 0; // “父节点”（懒标记）清零
}
int m = (tree[k].l tree[k].r) >> 1;
if(x <= m) Interval_modification(k << 1, x, y, z);
if(y > m) Interval_modification(k << 1 | 1, x, y, z);
tree[k].w = tree[k << 1].w tree[k << 1 | 1].w; // 存放更新后的值
}加上了懒标记之后，相应的单点查询、区间修改都要加上判断懒标记的条件，即：
代码语言：javascript复制if(tree[k].f) down(k); 线段树多做做就好啦，QWQ。
