线段树

Part 1

线段树是一个二叉搜索树（那么一个非叶子节点的左儿子下标就是2*当前节点的下标，右儿子就+1）
我们用一个数组tree[]模拟线段树，对于每个线段树下标node，tree[node]代表对应区间内的某个信息（和，积，最大最小值）。
Tips：对于一个node，如何知道tree[node]对应的是哪段区间？我们并不用关心这个信息，因为我们会在进行操作时计算。

Part 2

一般我们较为关心区间查询和区间修改（毕竟通过这两个操作也可以进行单点操作，原理也是一样的
建一个树

建树

void build(ll node,ll l,ll r){
	lazy[node]=0;
	if(l==r){
		tree[node]=a[l];
		return;
	}
	ll mid=(l+r)>>1;
	build(node<<1,l,mid);
	build(node<<1|1,mid+1,r);
	tree[node]=tree[node<<1]+tree[node<<1|1];
}

懒标记下传

void push_down(ll node,ll l,ll r){
	ll mid=(l+r)>>1;
	f(node<<1,lazy[node],l,mid);
	f(node<<1|1,lazy[node],mid+1,r);
	lazy[node]=0;
}

区间修改

我们定义一个update_range(nl,nr,l,r,node,k)函数代表区间修改。
nl与nr代表需要修改的区间，l与r代表当前区间（解决了Part 1的问题），node代表当前区间下标，k代表进行操作的值。

void update(ll node,ll nl,ll nr,ll l,ll r,ll k){
	if(nl<=l&&r<=nr){//当前区间被所需区间覆盖
		tree[node]+=(r-l+1)*k;
		lazy[node]+=k;//打上懒标记
		return;
	}
	push_down(node,l,r);//lazy下传
	ll mid=(l+r)>>1;
	if(nl<=mid)update(node<<1,nl,nr,l,mid,k);//递归左儿子。边界背就好了
	if(nr>mid)update(node<<1|1,nl,nr,mid+1,r,k);//右儿子
	tree[node]=tree[node<<1]+tree[node<<1|1];//上传（维护一下
}

区间查询

和update差不多，就是把k丢掉

ll query_range(ll nl,ll nr,ll l,ll r,ll node){
	ll res=0;
	if(nl<=l&&r<=nr)return tree[node];
	ll mid=(l+r)>>1;
	push_down(node,l,r);//也要将懒标记下传啊
	if(nl<=mid)res+=query_range(nl,nr,l,mid,node<<1);
	if(nr>mid)res+=query_range(nl,nr,mid+1,r,node<<1|1);
	return res;
}

关于懒标记网上总结的非常全面

线段树

原文：https://www.cnblogs.com/ttt1493b/p/14369833.html