线段树的本质，是一种加快运算速度的数据结构，将一串数字不断从中间分开的方式，知道分成一棵二叉树。可以将某区间需要求的答案保存在父节点上，再通过搜索二叉树求得答案。（据说）所有可有用树状数组解决的问题都可以用线段树解决，尤其是区间修改区间查询等操作，而且也不会慢太多。

一、用图看一下？

图中x,y表示x到y的一段区间，我们很容易看出来，是把1——10的一段序列拆成二叉树的形式了。

需要把下面子节点的信息，通过递归存储到父节点上，这样求取区间信息的时候就很方便。

当我们需要修改区间时（单点看做最下面的一段小区间，同理），在这个区间对应的根上打标记，

等到需要查询这个区间（单点）时，再向下查。因为是从大区间向小区间查，所以每次循环点的编

号找到的一定是符合条件的最大区间。

二、怎么整？

1.建树

1.建一个结构体，把一个点(root：点的编号)的各个信息都存下来。

struct tree{
	int ll,rr,anss,mark;
}a[40005];//需要开四倍空间！
//ll表示这个区间的左端点
//rr表示这个区间的右端点
//anss表示这一段区间的答案（范围为根下属子树）这里举例为这段区间的最大值
//mark表示标记过该点的修改值（如+1，mark=1，表示差值）

 2.通过递归，将一个已知的数组拆成二叉树。递归边界是l=r，易得此时的区间为（x,x），即递归到了单个数字，就可以返回了。

3.每次修改mid=（l+r）/ 2 ,向左右两边建这科树。

4.很容易观察得到左边节点为root*2,右边节点为root*2+1。

void build(int l,int r,int root){
	a[root].ll=l;
	a[root].rr=r;
	if(l==r){
		a[root].anss=b[l];
	} 
	int mid=(l+r)/2;
	build(l,mid,root*2);
	build(mid+1,r,root*2+1);
	a[root].anss=max(a[root*2].anss,a[root*2+1].anss);
}
//b[i]是输入数组,表示原序列 

2.更新数字（举例：把该点数字+1）

1.从第一个root开始搜（此时root=1）,如果要修改的区间就在这个root的大区间中，就把这个root的值先进行修改（本例子中求最大值，所有数+1，最大值也+1，所以anss直接+1），并且打上标记（mark+1，意味着如果之后需要求解root的子区间的最大值，就需要在向下搜到答案区间时，加上沿途的mark）。

2.如果需要求解的区间不在这个root的区间中，就向下搜，并且加上沿途的mark（进行过这个操作时，所有数的mark就都进行了更新，维护了mark是下面子树要加的值这个性质），顺便更新anss。

void update(int l,int r,int root){
	if(l<=a[root].ll&&a[root].rr<=r){
        //因为是从大区间向小区间查，所以每次循环点的编号找到的一定是符合条件的最大区间。
		a[root].anss+=1;
		a[root].mark+=1;
	}
	else{
		godown(root);//这个函数待会儿说
		int mid=(a[root].ll+a[root].rr)/2;
		if(l<=mid)//说明左子树上有需要操作的区间
			update(l,r,root*2);
		if(r>mid)//同理
			update(l,r,root*2+1);
		a[root].anss=max(a[root*2].anss,a[root*2+1.anss]);	 
	}
}

3.打标记的维护函数godown

1.维护root的mark是它的子区间mark的和，子区间的anss需要加上父亲节点的mark。

2.为了避免向下搜索时出现断层，要每次手动操作将root的两个直接的儿子赋值。

3.使用完时候将root的mark赋值为0，避免重复加1。

void godown(int root){
	if(a[root].mark!=0){
		a[root*2].mark+=a[root].mark;
		a[root*2+1].mark+=a[root].mark;
		a[root*2].anss+=a[root].mark;
		a[root*2+1].anss+=a[root].mark;
		a[root].mark=0;
	}
} 

 4.求最大值

把之前的mark加上，求值

void maxx(int l,int r,int root){
	int mid=(a[root].ll+a[root].rr)/2;
	int anss=-0x3f3f3f3f;
	if(l<=a[root].ll&&s[root].rr<=r){
		//因为是从大区间向小区间查，所以每次循环点的编号找到的一定是符合条件的最大区间。
		return a[root].anss;
	}
	else{
		godown(root);//在求值前记得把mark上的值加上 
		if(l<=mid)ans=max(ans,maxx(l,r,root*2));
		if(r>mid)ams=max(ans,maxx(l,r,root*2+1));
		return ans; 
	}
}

 三.我们来看一下最终版？

题目描述

给定一个数列，初值全为0，现对这个序列有两种操作：

操作1：将第k1 个数 到 第k2 个数加1；

操作2：查询 从第k1个数到第k2个数得最大值。

输入格式

第一行给定一个整数n，表示有n个操作。

以下接着n行，每行三个整数，表示一个操作。

输出格式

若干行，查询一次，输出一次。

#include<bits/stdc++.h>
using namespace std;
int b[400005],n,k1,k2,s;
struct emm{
	int ll,rr,anss,mark;
}a[400005];
void build(int root,int l,int r){
	a[root].ll=l;
	a[root].rr=r;
	if(l==r){
		a[root].anss=b[l];
		return;
	}
	int mid=(l+r)/2;
	build(root*2,l,mid);
	build(root*2+1,mid+1,r);
	a[root].anss=max(a[root*2].anss,a[root*2+1].anss);	
}
void godown(int root){
	if(a[root].mark!=0){
		a[root*2].mark+=a[root].mark;
		a[root*2+1].mark+=a[root].mark;
		a[root*2].anss+=a[root].mark;
		a[root*2+1].anss+=a[root].mark;
		a[root].mark=0;
	}
}
void update(int root,int l,int r){
	if(l<=a[root].ll&&a[root].rr<=r){
		a[root].anss+=1;
		a[root].mark+=1;
		return;
	}
	else{
		godown(root);
		int mid=(a[root].ll+a[root].rr)/2;
		if(l<=mid)update(root*2,l,r);
		if(r>mid)update(root*2+1,l,r);
		a[root].anss=max(a[root*2].anss,a[root*2+1].anss);
	}
	
}
int maxx(int root,int l,int r){
	int ans=-0x3f3f3f3f;
	int mid=(a[root].ll+a[root].rr)/2;
	if(l<=a[root].ll&&a[root].rr<=r){
		return a[root].anss;
	}else{
		godown(root);
		if(l<=mid)ans=max(ans,maxx(root*2,l,r));
		if(r>mid)ans=max(ans,maxx(root*2+1,l,r));
		return ans;
	}
	
}
int main(){
	scanf("%d",&n);
	build(1,1,n); 
	for(int i=1;i<=n;i++){
		scanf("%d%d%d",&s,&k1,&k2);
		if(s==1)update(1,k1,k2);
		if(s==2)printf("%d\n",maxx(1,k1,k2));
	}
	return 0;
}