线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。
使用线段树可以快速的查找某一个节点在若干条线段中出现的次数，时间复杂度为O(logN）。
因为线段树的时间复杂度比较低，所以一旦看到题中出现求区间值（和，最大/小值，乘积，取模，区间修改等等），我一般首选线段树，就算拿不到满分一般也可以得到七十分，如果加入优化的话甚至可以拿满分，比暴力好多了→ →。

1. 什么是线段树？

你可以将一列数看做一条线段，从中间开始不断分成两半，直到分到最终的每一个节点，比如从1~10的十个数，我们可以建立如下图的线段树

每一个区间【l,r】都代表了区间l到r的记录值，比如区间和啊，区间最小值之类的。

2.怎么建线段树？

建树函数build ( root , l , r )
一开始root作为根节点1，然后我们将1记做root的左儿子l，n记做右儿子r，同时还要用lc / rc表示左 / 右儿子的节点。
mid=（l+r/）2，那么我们接下来要建的就是( lc , l ,mid ）和( rc , mid+1 , r)。
在这样一层一层建树之后，我们来到最下面一层，也就是当 l = = r 的时候，我们相当于搜的是一个点，然后记录这个点的各种值，返回，并且在返回过程中一层一层更新每一个节点的各种值。
建树函数如下：

//（我用x来表示root，tot表示节点，记录的是每一个区间的区间和sum以及最大值ma）
const int N=300001;
struct node{
	int l,r,lc,rc;
	long long sum,mark,ma;
}t[N];
void build(int x,int l,int r)
{
	t[x].l=l; t[x].r=r;
	if(l==r)
	{
		t[x].sum=a[l];
		t[x].ma=a[l];
		return ;
	} 
	int mid=(l+r)/2;
	t[x].lc=++tot; build(t[x].lc,l,mid);
	t[x].rc=++tot; build(t[x].rc,mid+1,r);
	t[x].sum=t[t[x].lc].sum+t[t[x].rc].sum;
	t[x].ma=max(t[t[x].lc].ma,t[t[x].rc].ma);
}

看懂了之后非常的简单易懂，对吧 (^o^)/ 【大雾
学会了建树，接下来的区间修改什么的就很容易理解了~

3.怎么区间修改？

区间修改是非常常见的，比如将 l ~ r 的所有值增加d之类的
那么首先我们很容易想到的是单点修改，就是和建树一样，一层一层搜到最底的点，然后更改它们的值，一层一层返回并在返回过程中修改区间值。
但是这样很麻烦并且时间复杂度会很高，所以我们机智地创造了lazy标记这种神奇的东西

以将 l ~ r 的所有值增加d为例，假设当我们搜索到【l1,r1】时，发现l1~r1包括在了l~r的范围内，那么这时我们就可以只更改【l1,r1】区间的值，并且给这个区间加一个标记记录它的修改值d，表示我们只搜到了这个区间，然后我们就停下来，不用再向下修改了。因为对于这一次查询来说，我们只需要这个区间的值就够了。
那么问题在于，当下一次修改时，我们需要用到【l1,r1】一下的节点该怎么办？
我们只需要将【l1,r1】的lazy标记继续向下传递，并将它本身的标记归零，这样我们就可以继续向下修改了~
好了，修改函数如下：


void push(int x)
{
	if(t[x].mark==0) return ;
	int M=t[x].mark,l=t[x].lc,r=t[x].rc;
	t[l].mark+=M; t[l].sum+=M*(t[l].r-t[l].l+1); t[l].ma+=M;
	t[r].mark+=M; t[r].sum+=M*(t[r].r-t[r].l+1); t[r].ma+=M;
	t[x].mark=0;
}
//push函数就是将lazy标记向下传递的
void add(int x,int l,int r,int d)
{
	if(l<=t[x].l&&r>=t[x].r)
	{
		t[x].mark+=d;
		t[x].sum+=d*(t[x].r-t[x].l+1);
		t[x].ma+=d;
		return ;
	}
	push(x);
	int mid=(t[x].l+t[x].r)/2;
	if(l<=mid) add(t[x].lc,l,r,d);
	if(r>mid)  add(t[x].rc,l,r,d); 
	t[x].sum=t[t[x].lc].sum+t[t[x].rc].sum;	
	t[x].ma=max(t[t[x].lc].ma,t[t[x].rc].ma);
}

4.关于线段树的类型问题

无非就是和，最大/小值，乘积，取模，区间修改这些，我写了一个求区间和，区间修改，最大值的线段树模板，附上，如有错误请轻拍并告诉我= =

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
const int N=300001;
int m,n,x,y,z,a[N],tot;
char w;
struct node{
	int l,r,lc,rc;
	long long sum,mark,ma;
}t[N];
void build(int x,int l,int r)
{
	t[x].l=l; t[x].r=r;
	if(l==r)
	{
		t[x].sum=a[l];
		t[x].ma=a[l];
		return ;
	} 
	int mid=(l+r)/2;
	t[x].lc=++tot; build(t[x].lc,l,mid);
	t[x].rc=++tot; build(t[x].rc,mid+1,r);
	t[x].sum=t[t[x].lc].sum+t[t[x].rc].sum;
	t[x].ma=max(t[t[x].lc].ma,t[t[x].rc].ma);
}
void push(int x)
{
	if(t[x].mark==0) return ;
	int M=t[x].mark,l=t[x].lc,r=t[x].rc;
	t[l].mark+=M; t[l].sum+=M*(t[l].r-t[l].l+1); t[l].ma+=M;
	t[r].mark+=M; t[r].sum+=M*(t[r].r-t[r].l+1); t[r].ma+=M;
	t[x].mark=0;
}
int query(int x,int l,int r)
{
	if(l<=t[x].l&&t[x].r<=r)
	{
		return t[x].sum;
	}
	push(x);
	int ans=0;
	int mid=(t[x].l+t[x].r)/2;
	if(l<=mid) ans+=query(t[x].lc,l,r);
	if(r>mid)  ans+=query(t[x].rc,l,r);
	return ans;
}
void add(int x,int l,int r,int d)
{
	if(l<=t[x].l&&r>=t[x].r)
	{
		t[x].mark+=d;
		t[x].sum+=d*(t[x].r-t[x].l+1);
		t[x].ma+=d;
		return ;
	}
	push(x);
	int mid=(t[x].l+t[x].r)/2;
	if(l<=mid) add(t[x].lc,l,r,d);
	if(r>mid)  add(t[x].rc,l,r,d); 
	t[x].sum=t[t[x].lc].sum+t[t[x].rc].sum;	
	t[x].ma=max(t[t[x].lc].ma,t[t[x].r].ma);
}
int compare(int x,int l,int r)
{
	if(t[x].l>=l&&t[x].r<=r)
	{
		return t[x].ma;
	}
	push(x);
	int mid=(t[x].l+t[x].r)/2,maxx=0;
	if(l<=mid) maxx=max(maxx,compare(t[x].lc,l,r));
	if(r>mid)  maxx=max(maxx,compare(t[x].rc,l,r));
	return maxx;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i) scanf("%d",&a[i]);
	tot=1;
	build(1,1,n);
	for(int i=1;i<=m;++i)
	{
		cin>>w;
		if(w=='s') //sum求区间和 
		{
			scanf("%d%d",&x,&y);
			cout<<query(1,x,y)<<endl;
			
		}
		if(w=='a') //add在区间内的所有数增加z 
		{
			scanf("%d%d%d",&x,&y,&z);
			add(1,x,y,z);
		}
		if(w=='c') //compare求区间内最大的数 
		{
			scanf("%d%d",&x,&y);
			cout<<compare(1,x,y)<<endl;
		}
	}
	return 0;
}

5.【模板】线段树

这道题可以当做线段树裸题来做，附上代码

#include<iostream>
#include<cstdio>
using namespace std;
const int N=2000001;
int n,m,a[N],tot;
struct node{
	int l,r,lc,rc,mark;
	long long sum;
}t[N];
void build(int x,int l,int r)
{
	t[x].l=l; t[x].r=r;
	if(l==r)
	{
		t[x].sum=a[l];
		return ;
	}
	int mid=(l+r)/2;
	t[x].lc=++tot; build(t[x].lc,l,mid);
	t[x].rc=++tot; build(t[x].rc,mid+1,r);
	t[x].sum=t[t[x].lc].sum+t[t[x].rc].sum;
}
void push(int x)
{
	if(t[x].mark==0) return ;
	int l=t[x].lc,r=t[x].rc,ma=t[x].mark;
	t[l].mark+=ma; t[l].sum=t[l].sum+ma*(t[l].r-t[l].l+1);
	t[r].mark+=ma; t[r].sum=t[r].sum+ma*(t[r].r-t[r].l+1);
	t[x].mark=0;
}
long long query(int x,int l,int r)
{
	if(l<=t[x].l&&t[x].r<=r)
	{
		return t[x].sum;
	}
	push(x);
	long long ans=0;
	int mid=(t[x].l+t[x].r)/2;
	if(l<=mid) ans=ans+query(t[x].lc,l,r);
	if(r>mid)  ans=ans+query(t[x].rc,l,r);
	return ans;
}
void add(int x,int l,int r,int d)
{
	if(l<=t[x].l&&t[x].r<=r)
	{
		t[x].mark+=d;		
		t[x].sum=t[x].sum+d*(t[x].r-t[x].l+1);
		return ;
	}
	push(x);
	int mid=(t[x].l+t[x].r)/2;
	if(l<=mid) add(t[x].lc,l,r,d);
	if(r>mid)  add(t[x].rc,l,r,d);
	t[x].sum=t[t[x].lc].sum+t[t[x].rc].sum;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i)
		scanf("%d",&a[i]);
	tot=1;
	build(1,1,n);
	int k,a1,b1,c;
	for(int i=1;i<=m;++i)
	{
		scanf("%d",&k);
		if(k==1)
		{
			scanf("%d%d%d",&a1,&b1,&c);
			add(1,a1,b1,c);
		} 
		else
		{
			scanf("%d%d",&a1,&b1);
			printf("%lld\n",query(1,a1,b1));
		} 
	}
	return 0;
}

6.【例题】小W 开关灯

【题目描述】
晚上到家小 W 通过开关灯来保持自己神经的兴奋以便清醒地理笔记。
N(2≤N≤100,000)盏灯被连续的编号为1..N。刚回到家的时候,所有的灯都是关闭的。
小 W 通过 N个按钮来控制灯的开关，按第i个按钮可以改变第 i 盏灯的状态。
小 W 发出 M (1≤M≤100,000)条指令,每个指令都是两个整数中的一个(0 或 1)。
第 1 种指令(用 0 表示)包含两个数字S_i和 E_i(1≤S_i≤E_i≤N)，它们表示起始开
关和终止开关。小 W需要把从 S_i 到 E_i 之间的按钮都按一次,就可以完成这个指令。
第2种指令(用 1 表示)同样包含两个数字S_i和E_i(1≤S_i≤E_i≤N),不过这种指令
是询问从 S_i到 E_i之间的灯有多少是亮着的。
请你帮助小 W 得到正确的答案。

【输入格式】
第 1 行: 用空格隔开的两个整数 N 和 M。
第 2..M+1 行: 每行表示一个操作, 有三个用空格分开的整数: 指令号, S_i 和 E_i。

【输出格式】
对于每一次询问, 输出一行表示询问的结果。

【输入输出样例】
note.in
4 5
0 1 2
0 2 4
1 2 3
0 2 4
1 1 4

note.out
1
2

基本的线段树的区间修改和区间查询操作。
记录区间开灯数，区间是否完全改变，并下传区间改变标记即可。
lazy标记不是很好改，容易写错，多写写完全理解就好了，注意它的传递方式。虽然线段树不是noip考试范围，而且不会考到lazy…………但是谁知道呢(╯‵□′)╯︵┻━┻

#include<iostream>
#include<cstdio>
using namespace std;
const int N=2000000;
int n,m,tot;
struct node{
	int l,r,lc,rc,sum,mark;
}t[N];
inline void build(int x,int l,int r)
{
	t[x].l=l;t[x].r=r;
	if(l==r)
	{
		t[x].sum=0;
		return ;
	}
	int mid=(l+r)/2;
	t[x].lc=++tot; build(t[x].lc,l,mid);
	t[x].rc=++tot; build(t[x].rc,mid+1,r);
}
inline void lazy(int x)
{
	int l=t[x].lc,r=t[x].rc,m=t[x].mark;
	if(m%2==0) 
	{
		t[x].mark=0;
		return ;
	}
	else
	{
		t[l].mark+=m; t[l].sum=(t[l].r-t[l].l+1)-t[l].sum;
		t[r].mark+=m; t[r].sum=(t[r].r-t[r].l+1)-t[r].sum;
		t[x].mark=0;
		return ;
	}
}
inline void change(int x,int l,int r)
{
	if(l<=t[x].l&&t[x].r<=r)
	{
		t[x].mark++;
		t[x].sum=(t[x].r-t[x].l+1)-t[x].sum;
		return ;
	}
	lazy(x);
	int mid=(t[x].l+t[x].r)/2;
	if(l<=mid) change(t[x].lc,l,r);
	if(r>mid)  change(t[x].rc,l,r);
	t[x].sum=t[t[x].lc].sum+t[t[x].rc].sum;
}
inline int query(int x,int l,int r)
{
	if(l<=t[x].l&&t[x].r<=r)
	{
		return t[x].sum;
	}
	lazy(x);
	int mid=(t[x].l+t[x].r)/2,ans=0;
	if(l<=mid) ans+=query(t[x].lc,l,r);
	if(r>mid)  ans+=query(t[x].rc,l,r);
	return ans;
}
int main()
{
	freopen("lites.in","r",stdin);
	freopen("lites.out","w",stdout);
	scanf("%d%d",&n,&m);
	tot=1;
	build(1,1,n);
	for(int i=1;i<=m;++i)
	{
		int h,s,e;
		scanf("%d%d%d",&h,&s,&e);
		if(h==0)
		{
			change(1,s,e);
		}
		else
		{
			printf("%d\n",query(1,s,e));
		}
	}
	return 0;
}