Segment Tree——线段树入门

线段树是一种基于分治思想的二叉树结构，用于在区间上进行统计。每个节点代表一个区间，对于每个内部节点[l,r]（编号p），左子节点代表区间[l,mid]（编号p2），右子节点代表区间[mid+1,r]（编号p2+1）.可以用结构体数组保存一棵线段树，数组大小开到N*4

struct segment_tree
{
	int l,r;
	long long sum;
}tree[100010*4];

void build(int p,int l,int r)
{
	tree[p].l=l,tree[p].r=r,tree[p].sum=0;
	if(l==r) return;//到达根节点 
	int mid=(l+r)/2;
	build(p*2,l,mid);//左子树 
	build(p*2+1,mid+1,r);//右子树 
}

void change(int p,int x,int v)
{
	if(tree[p].l==tree[p].r)//到达对应单点（左右端点值都为x） 
	{
		tree[p].sum+=v;//修改 
		return;
	}
	int mid=(tree[p].l+tree[p].r)/2;
	if(x<=mid) change(p*2,x,v);//单点在左子树 
	else change(p*2+1,x,v);//单点在右子树 
	tree[p].sum=(tree[p*2].sum+tree[p*2+1].sum);//合并 
}

假设当前询问的区间为[l,r]
递归到一个区间[tl,tr]时,有四种情况：

1. l < = t l < = t r < = r l<=tl<=tr<=r l<=tl<=tr<=r,该区间被完全覆盖在询问区间内，直接返回[tr,tl]上的和；
2. t l < = l < = t r < = r tl<=l<=tr<=r tl<=l<=tr<=r,当前区间的右边一部分在询问区间内，判断l与mid=(tr+tl)/2的大小关系，若l>mid，只需递归右子树，否则需要递归左右子树（右子树会在递归后直接返回）
3. l < = t l < = r < = t r l<=tl<=r<=tr l<=tl<=r<=tr,参考上一条
4. t r < = l < = r < = t r tr<=l<=r<=tr tr<=l<=r<=tr，递归左右子树

long long ask(int p,int l,int r)
{
    if(l<=tree[p].l&&r>=tree[p].r) 
		return tree[p].sum;//如果整个区间被覆盖，就返回维护的值
    int mid=(tree[p].l+tree[p].r)>>1;
    long long ans=0;
    if(l<=mid) ans+=ask(p*2,l,r);
    if(r>mid) ans+=ask(p*2+1,l,r);//累加答案，返回左右儿子的和
    return ans;
}

#include
using namespace std;

struct segment_tree
{
	int l,r;
	long long sum;
}tree[100010*4];

void build(int p,int l,int r)
{
	tree[p].l=l,tree[p].r=r,tree[p].sum=0;
	//cout<<"p:"<
	if(tree[p].l==tree[p].r)//到达对应单点（左右端点值都为x） 
	{
		tree[p].sum+=v;//修改 
		return;
	}
	int mid=(tree[p].l+tree[p].r)/2;
	if(x<=mid) change(p*2,x,v);//单点在左子树 
	else change(p*2+1,x,v);//单点在右子树 
	tree[p].sum=(tree[p*2].sum+tree[p*2+1].sum);//合并 
}

long long ask(int p,int l,int r)
{
    if(l<=tree[p].l&&r>=tree[p].r) 
		return tree[p].sum;//如果整个区间被覆盖，就返回维护的值
    int mid=(tree[p].l+tree[p].r)>>1;
    long long ans=0;
    if(l<=mid) ans+=ask(p*2,l,r);
    if(r>mid) ans+=ask(p*2+1,l,r);//累加答案，返回左右儿子的和
    return ans;
}
int main()
{
	int n,m;
	scanf("%d %d",&n,&m);
	build(1,1,n);
	for(int i=1;i<=m;i++)
	{
		char c; int x,y;
		cin>>c>>x>>y;
		if (c=='x') change(1,x,y);//单点修改 
		if (c=='y') printf("%lldn",ask(1,x,y));//区间查询 
	}
	return 0;
}

之前遇到区间修改时可能会遍历区间内的所有数，效率极其低下，有了线段树这种每个结点代表一个区间的数据结构，我们可以在结构体里新增一个变量add，用于储存对区间的增值操作，在未访问到这个区间时，我们可以不用管（这样就省掉了很多无用功233），如果访问到这个区间，就把这个区间对应的sum值加上（add*区间内点数），将add下放到左右两个子树，再将当前节点的add归零。
延迟标记的含义为“该节点曾经被修改，但其子节点尚未被更新”，其本身信息已被修改完毕。

void spread(int p)
{
	if(tree[p].add!=0)
	{
		tree[p*2].sum+=(tree[p*2].r-tree[p*2].l+1)*tree[p].add;=
		tree[p*2+1].sum+=(tree[p*2+1].r-tree[p*2+1].l+1)*tree[p].add;=
		tree[p*2].add+=tree[p].add;
		tree[p*2+1].add+=tree[p].add;
		tree[p].add=0;
	}
}

#include
using namespace std;

int n,m,a[100010];

struct segment_tree
{
	int l,r;
	long long sum,add;
}tree[100010*4];

void build(int p,int l,int r)
{
	tree[p].l=l,tree[p].r=r;
	if(l==r)
	{
		tree[p].sum=a[l];
		return;
	}
	int mid=(l+r)/2;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
	tree[p].sum=tree[p*2].sum+tree[p*2+1].sum;
}

void spread(int p)
{
	if(tree[p].add!=0)
	{
		tree[p*2].sum+=(tree[p*2].r-tree[p*2].l+1)*tree[p].add;=
		tree[p*2+1].sum+=(tree[p*2+1].r-tree[p*2+1].l+1)*tree[p].add;=
		tree[p*2].add+=tree[p].add;
		tree[p*2+1].add+=tree[p].add;
		tree[p].add=0;
	}
}

void change(int p,int l,int r,int x)
{
	if(l<=tree[p].l&&r>=tree[p].r)
	{
		tree[p].sum+=(long long)x*(tree[p].r-tree[p].l+1);
		tree[p].add+=x;
		return;
	}
	spread(p);//延迟标记
	int mid=(tree[p].l+tree[p].r)/2;
	if(l<=mid) change(p*2,l,r,x);
	if(r>mid) change(p*2+1,l,r,x);
	tree[p].sum=tree[p*2].sum+tree[p*2+1].sum;
}

long long ask(int p,int l,int r)
{
    if(l<=tree[p].l && r>=tree[p].r) 
		return tree[p].sum;//如果被覆盖，就返回维护的值
    spread(p);//下传延迟标记，并查询左右儿子
    int mid=(tree[p].l+tree[p].r)>>1;
    long long ans=0;
    if(l<=mid) ans+=ask(p*2,l,r);
    if(r>mid) ans+=ask(p*2+1,l,r);//累加答案，返回左右儿子的和
    return ans;
}

int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	build(1,1,n);
	while(m--)
	{
		int op,l,r;
		scanf("%d%d%d",&op,&l,&r);
		if(op==1)
		{
			int x;
			scanf("%d",&x);
			change(1,l,r,x);
		}
		else if(op==2)
			printf("%lldn",ask(1,l,r));
	}
	return 0;
}

如果有更多种操作（乘上一个值等）可以在结构体再开别的变量，保存标记信息，但需要各个标记下放的顺序。