【模板】线段树

以维护区间和为例，这里的线段树为结构体的数组，因为我觉得用结构体思路比较清晰

变量声明：

a[]:原序列
struct node{
	int l;
	int r;	//l,r:该结点维护的区间 
	int num; //该结点维护的区间值 
	int add; //懒标记 
}tree[N*4+1]; //线段树数组

建树：

void build(int k,int l,int r)
//k:当前结点 l,r:当前结点维护的区间
{
   tree[k].l=l;
   tree[k].r=r;//以k为编号的节点维护的区间为l到r
   if (l==r)//当前结点为叶子结点 
   {
   	   tree[k].num=a[l];//对应区间的值为原序列中的对应值 
   	   return;
   }  //否则维护的值等于左儿子加右儿子
   int mid=(l+r)/2;
   build(k*2,l,mid); //构造左子树 
   build(k*2+1,mid+1,r); //构造右子树 
   tree[k].num=tree[k*2].num+tree[k*2+1].num; 
   //自下向上更新，该结点的值等于左儿子的值加上右儿子的值 
} 

单点修改,区间查询：

void change_point(int k,int x,int v) //单点修改 
//k:当前结点 x:原序列的位置 v:需要修改的值 
{
	if (tree[k].r<x||tree[k].l>x) return; //当前区间与原序列的位置完全无交集
	if (tree[k].l==x&&tree[k].r==x) //当前结点为对应的叶子结点
	{
	    tree[k].num+=v;
		return;	
	} 
	change_point(k*2,x,v);//修改左子区间 
	change_point(k*2+1,x,v); //修改右子区间
	tree[k].num=tree[k*2].num+tree[k*2+1].num;//更新相关的值 
}

long long search(int k,int x,int y) //区间查询
//k:当前结点 x,y:查询区间 
{
	if (y<tree[k].l||x>tree[k].r) return 0;//当前区间与原序列的位置完全无交集,返回一个不影响答案的值 
	if (tree[k].l>=x&&tree[k].r<=y) return tree[k].num; //询问区间在当前区间，返回维护好的值
	return search(k*2,x,y)+search(k*2+1,x,y); 
}

区间修改，区间查询：

void Add(int k,int v) //给结点k维护的区间加上v 
{
	tree[k].add+=v;//打标记
	tree[k].num+=(tree[k].r-tree[k].l+1)*(long long)v;//维护对应的区间和，即将当前区间包含的数的个数*要加上的数 
	return;
}
void spread(int k) //标记下传 
//k:当前结点 
{
	if (tree[k].add==0) return; //如果没有标记，就不用考虑
	Add(k*2,tree[k].add);
	Add(k*2+1,tree[k].add);
	tree[k].add=0; //注意，当标记下传后，当前结点的标记要清零 
} 
void build(int k,int l,int r) //建树 
//k:当前结点 l,r:当前结点维护的区间
{
   tree[k].l=l;
   tree[k].r=r;//以k为编号的节点维护的区间为l到r
   if (l==r)//当前结点为叶子结点 
   {
   	   tree[k].num=a[l];//对应区间的值为原序列中的对应值 
   	   return;
   }  //否则维护的值等于左儿子加右儿子
   int mid=(tree[k].l+tree[k].r)/2;
   build(k*2,l,mid); //构造左子树 
   build(k*2+1,mid+1,r); //构造右子树 
   tree[k].num=tree[k*2].num+tree[k*2+1].num; //自下向上更新，该结点的值等于左儿子的值加上右儿子的值 
} 
void change_part(int k,int x,int y,int v)
//k:当前结点 x,y:修改区间 v:要加上的数 
{
    if (x<=tree[k].l&&tree[k].r<=y)//当前结点维护的区间被覆盖的话，就对其进行修改 
    { 
    	Add(k,v);//给结点k维护的区间加上v
	    return;
	}
	spread(k); //如果发现没有被覆盖，那就需要继续向它包含的两个区间找，考虑儿子所维护的区间可能因为懒标记的存在而没有修改，因此将懒标记下放
    int mid=(tree[k].l+tree[k].r)/2;
    if (x<=mid) change_part(k*2,x,y,v);//如果要修改的区间覆盖了左子树，就修改左子树
	if (y>mid) change_part(k*2+1,x,y,v); // 如果要修改的区间覆盖了右子树，就修改右子树
    tree[k].num=tree[k*2].num+tree[k*2+1].num;//维护当前区间 
}
long long query(int k,int x,int y) //查询区间x,y的和
{
	if (x<=tree[k].l&&tree[k].r<=y) return tree[k].num;//如果当前区间被覆盖，就返回当前区间维护的值 
	spread(k); //下传懒标记 
	int mid=(tree[k].l+tree[k].r)/2;
	long long anss=0;
	if (mid>=x) anss+=query(k*2,x,y);//如果要查询的区间覆盖了左子树，就查询左子树
    if (mid<y) anss+=query(k*2+1,x,y);//如果要查询的区间覆盖了右子树，就查询右子树
    return anss;
} 

不断地练习才能巩固线段树啊，不知查询区间和，还有查询区间最值，区间乘法之类的，路漫漫其修远兮，加油吧少年

镇楼：