线段树模板

线段树属于高级数据结构，本文粗略地讲解了一下线段树的模板，大家直接拿去用就好。

long long ls(int x){return x<<1;}
long long rs(int x){return x<<1|1;}
const int kmax = 1e5 + 10;
struct segmenttree
{
	long long l,r;//区间d左值，右值
	long long sum;//区间和
	long long lazy;//懒惰标记
}t[kmax<<2]；

long long a[kmax];
void pushup(int p)
{//区间和等于左半部分区间和加右半部分区间和
	t[p].sum = t[p<<1].sum + t[p<<1|1].sum;
}

void pushdown(int p)
{
	if(t[p].lazy){
	//如果有懒惰标志,则向下传递
	t[ls(p)].sum += t[p].lazy * (t[ls(p)].r - t[ls(p)].l + 1);
	t[rs(p)].sum += t[p].lazy * (t[rs(p)].r - t[rs(p)].l + 1);
	t[ls(p)].lazy += t[p].lazy;
	t[rs(p)].lazy += t[p].lazy;
	t[p].lazy = 0;
	}
}
void bulid(long long p,long long l,long long r)
{//建树，调用方式build(1,1,n);
	t[p].l = l,t[p].r = r;
	if(l==r)//如果到达叶节点，则他的值等于原数组中的数
	{
		t[p].sum = a[l];
		return;
	}
	long long mid = (l+r)>>1;//否则递归左半右半区间
	build(ls(p),l,mid);
	build(rs(p),mid + 1,r);
	pushup(p);
}

void change(long long p,long long l,long long r,long long d)
{//区间修改，调用方式change(1,l,r,d);
	if(l<=t[p].l&&r>=t[p].r)//如果该区间完整覆盖了目标区间，修改并直接返回
	{
		t[p].sum += d * (t[p].r - t[p].l + 1);
		t[p].lazy += d;
		return;
	}
	pushdown(p);//否则向下传递懒惰标记，并递归左半右半区间
	long long mid = (t[p].l + t[p].r) / 2;
	if(l<=mid)change(ls(p),l,r,d);//如果有一部分在左区间，递归左区间
	if(r>mid)change(rs(p),l,r,d);//如果有一部分在右区间，递归右区间
	pushup(p);
}

long long query(long long p,long long l,long long r)//当前的结点编号
{//区间求和，调用方式query(1,l,r);
	if(l<=t[p].l&&r>=t[p].r)return t[p].sum;//如果该区间完整覆盖了目标区间，直接返回
	pushdown(p);//否则向下传递懒惰标记，并递归左半右半区间
	long long mid  = (t[p].l + t[p].r) / 2;
	long long sum = 0;
	if(l<=mid)sum+=query(ls(p),l,r);//如果有一部分在左区间，递归左区间
	if(r>mid)sum+=query(rs(p),d,l,r);
	return sum;//返回累加和
}