这篇讲讲线段树，个人认为直接上代码配注释好理解。。。

/*线段树：线段树，是一种二叉搜索树。它将一段区间划分为若干单位区间，每一个节点都储存着一个区间。
基本思想：二分
基础操作：建树 单点查询 单点修改 区间查询 区间修改
*/

include <stdio.h>

include <string.h>

include

include <math.h>

include

define N 200005

using namespace std;
struct node{
int l,r,w,f;//l,r为区间左右节点，w为区间和 f为懒标记
}tree[4*N]; //结构体开四倍空间

为什么要开四倍空间呢，这里带图稍微讲一下

int n,p,a,b,m,x,y,ans;
void down(int k);
/建树
① 主体思路：
a、对于二分到的每一个结点，给它的左右端点确定范围。
b、如果是叶子节点，存储要维护的信息。
c、状态合并。
*/
void build(int l,int r,int k)//建树 build
{
tree[k].l=l,tree[k].r=r;
if(tree[k].l==tree[k].r)
{
tree[k].w=tree[k].l;
return ;//不要漏了return 找到子节点后不需要继续递归
}
int mid=(tree[k].l+tree[k].r)/2;//计算左右子节点的边界
build(l,mid,2k);//递归到左孩子
build(mid+1,r,2k+1);//递归到右孩子
tree[k].w=tree[2k].w+tree[2*k+1].w;//状态合并 此节点的w=两个孩子的w之和
}

/*
单点查询 ask_point
①主体思路：
与二分查询法基本一致，如果当前枚举的点左右端点相等，即叶子节点，就是目标节点。
如果不是，因为这是二分法,所以设查询位置为x，当前结点区间范围为了l，r，中点为mid,
则如果x<=mid，则递归它的左孩子，否则递归它的右孩子
/
void ask_point(int k)
{
if(tree[k].l==tree[k].r)
{
ans=tree[k].w;
return ;
}
if(tree[k].f) down(k);//懒标记下传。只有不满足上面的if条件才执行，所以一定会用到当前节点的子节点（为什么会有这一步下文会解释，别急，慢慢看）
int mid=(tree[k].l+tree[k].r)/2;
if(x<=m) ask_point(2k);
else ask_point(2*k+1);
}

/*
单点修改 change_point
即更改某一个点的状态。例如：对第x个数加上y
①主体思路:
结合单点查询的原理，找到x的位置；根据建树状态合并的原理，修改每个结点的状态
*/

void change_point(int k)
{
if(tree[k].l==tree[k].r)
{
tree[k].w+=y;
return ;
}
if(tree[k].f) down(k);//懒标记下传。只有不满足上面的if条件才执行，所以一定会用到当前节点的子节点
int mid=(tree[k].l+tree[k].r)/2;
if(x<=mid) change_point(2k);
else change_point(2k+1);
tree[k].w=tree[2k].w+tree[2k+1].w;
}

/*
区间查询 ask_interval
即查询一段区间的状态，在引例中为查询区间[a,b]的和。
[l,r]为当前结点区间，[a,b]为待查询区间
分为三种情况：
a.当前节点区间的值全为答案中的一部分，此种情况我们可以直接加上当前结点区间的状态
b.当前节点区间的值部分为答案中的一部分，此种情况暂时不加，根据区间端点与中点的关系，选择递归左孩子或者右孩子，直至满足情况1
c.当前节点区间包含了待查找区间，跟情况二类似，看端点与中点关系

(enm...如果害不清楚的话自己画图画一下两个区间比较一下，自己动手理解会更深)
*/

void ask_interval(int k)
{
if(a<=tree[k].l&&b>=tree[k].r)
{
ans+=tree[k].w;
return ;
}
if(tree[k].f) down(k);//懒标记下传。只有不满足上面的if条件才执行，所以一定会用到当前节点的子节点
int mid=(tree[k].l+tree[k].r)/2;
if(a<=mid) ask_interval(2k);
if(b>m) ask_interval(2k+1);
}

/*
懒标记下传 down（此处解释参考了我当初自己学的时候看的一篇博客，自己总结概括能力还是太差了）
1、直观理解："懒"标记，懒嘛！用到它才动，不用它就睡觉。
2、作用：存储到这个节点的修改信息，暂时不把修改信息传到子节点。就像家长扣零花钱，你用的时候才给你，不用不给你。
3、实现思路（重点）：
a.原结构体中增加新的变量，存储这个懒标记。
b.递归到这个节点时，只更新这个节点的状态，并把当前的更改值累积到标记中。
注意是累积，可以这样理解：过年，很多个亲戚都给你压岁钱，但你暂时不用，所以都被你父母扣下了。
c.什么时候才用到这个懒标记？当需要递归这个节点的子节点时，标记下传给子节点。
这里不必管用哪个子节点，两个都传下去。就像你如果还有妹妹，父母给你们零花钱时总不能偏心吧
d.下传操作：
3部分：
①当前节点的懒标记累积到子节点的懒标记中。
②修改子节点状态。在引例中，就是原状态+子节点区间点的个数*父节点传下来的懒标记。
这就有疑问了，既然父节点都把标记传下来了，为什么还要乘父节点的懒标记，乘自己的不行吗？
因为自己的标记可能是父节点多次传下来的累积，每次都乘自己的懒标记造成重复累积
③父节点懒标记清0。这个懒标记已经传下去了，不清0后面再用这个懒标记时会重复下传。
就像你父母给了你5元钱，你不能说因为前几次给了你10元钱, 所以这次给了你15元，那你不就亏大了。

这也就是为什么上面包括下面几个函数有那条语句的原因。因为引入了懒标记，很多用不着的更改状态存了起来，这就会对区间查询、单点查询、单点修改造成一定的影响。
所以在使用了懒标记的程序中，单点查询、单点修改、区间查询也要像区间修改那样对用得到的懒标记下传。其实就是加上一句if(tree[k].f)  down（k），其余不变。
如果程序中未因 使用区间修改而是用了懒标记 其它三个函数可不加 if(tree[k].f)  down（k）

/
void down(int k)
{
tree[k2].f+=tree[k].f;
tree[k2+1].f+=tree[k].f;
tree[k*2].w+=tree[k].f(tree[k2].r-tree[k2].l+1);
tree[k2+1].w+=tree[k].f(tree[k2+1].r-tree[k2+1].l+1);
tree[k].f=0;
}

/*
区间修改
即修改一段连续区间的值，我们已给区间[a,b]的每个数都加y为例讲解
/
void change_interval(int k)
{
if(tree[k].l>=a&&tree[k].r<=b)//当前区间全部对要修改的区间有用
{
tree[k].w+=(tree[k].r-tree[k].l+1)y;//(r-l)+1区间点的总数
tree[k].f+=y;
return;
}
if(tree[k].f) down(k);//懒标记下传。只有不满足上面的if条件才执行，所以一定会用到当前节点的子节点
int mid=(tree[k].l+tree[k].r)/2;
if(a<=mid) change_interval(k2);
if(b>mid) change_interval(k2+1);
tree[k].w=tree[k2].w+tree[k2+1].w;//更改区间状态
}

int main()
{
scanf("%d",&n);//n个节点
build(1,n,1);
scanf("%d",&m);//m种操作
for(int i=1;i<=m;i++)
{
scanf("%d",&p);
ans=0;
if(p==1)
{
scanf("%d",&x);
ask_point(1);//单点查询,输出第x个数
printf("%d",ans);
}
else if(p==2)
{
scanf("%d%d",&x,&y);
change_point(1);//单点修改
}
else if(p==3)
{
scanf("%d%d",&a,&b);//区间查询
ask_interval(1);
printf("%d\n",ans);
}
else
{
scanf("%d%d%d",&a,&b,&y);//区间修改
change_interval(1);
}
}
return 0;
}