线段树如何详细解析？

本文共计1089个文字，预计阅读时间需要5分钟。

首先查看一道模板题：https://www.luogu.com.cn/problem/P3372

题目描述：已知一个数列，你需要进行以下两种操作：

1.将某区间每一个数加上k。

2.求出某区间的和。

先来看一道模板题：

www.luogu.com.cn/problem/P3372

题目描述：

已知一个数列，你需要进行下面两种操作：

1.将某区间每一个数加上k。

2.求出某区间每一个数的和。

一看是区间查询和区间更新的题，就很容易想到线段树——线段树就是用来解决区间类型的题的。

那么什么是线段树呢？假如我们把{1,5,4,2,3}存入线段树，会是这样：

（黑色是区间，蓝色是区间所有数的和，红色是下标）

根据这张图，不难得出：

左儿子的下标=父节点下标*2； 右儿子的下标=父节点下标*2+1

那么我们就可以以这个规律递归建树了。

void P(long long id){//sum是区间所有数的和 t[id].sum=t[id*2].sum+t[id*2+1].sum; } void build(long long id,long long l,long long r){//建树 t[id].l=l; t[id].r=r;//将左右端点赋值 if(l==r){ t[id].sum=arr[r]; }else{ long long mid=(l+r)/2;//二分递归建树 build(id*2,l,mid); build(id*2+1,mid+1,r); P(id);//更新父节点sum值 } }

区间查询也基本是同理。

区间更新有点不同，那就是需要懒标记来节省时间。