线段树 [模板] （一）

在开始之前，至读者：

如果你想静下心来真正的学学线段树，那不妨仔细看下去，认真思考，相信会对你有帮助。

 

首先，模板原题在这：Luogu [P3372] 【模板】线段树 1

那么让我们进入正题：线段树到底是什么？  线段树可以用来干什么？

一，简介线段树

线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。使用线段树可以快速的查找某一个节点在若干条线段中出现的次数，时间复杂度为O(logN)。            ——360百科

上面是百科的结果，但是对于初学者来说并不好理解，所以我来总结一下：

简而言之：1.线段树是一种树（二叉树），它具有树的结构特性。2.它是专门用来处理区间问题的（例如说区间求和啊，区间求最大最小值啊等等）。

如果还不好理解，那就看看图：

假设我们有一段区间[1,2,3,4,5,6,7,8,9,10];

那么绿色的叶子节点就代表单元区间，存储原数列，每一个蓝色的节点就代表一段区间（例如说根节点为1~10，代表从一到十，也就是整段区间）。

线段树工作时：子节点不断向父亲节点传递信息，父亲节点不断将子节点的信息合并。

所以说：线段树实际上就是运用了分块思想 ，达到了O(logN)的处理速度。

2.逐步学会线段树的构造及实现。（以区间求和为例）

 

（开始之前：最基本的思想：对于每一个编号为 i 的父亲节点，其左儿子为：2*i ，其右儿子为： 2*i+1）

我们可以先写一个O(1)的取儿子函数，便于阅读（其实不写也没事，只不过在之后会略微降低代码可读性）

int ls(int x){ return x1; f(ls(p),l,mid,tag[p]); //下放到左儿子 f(rs(p),mid+1,r,tag[p]); // 右儿子 tag[p]=0; //将当前节点标记置为零，这一步要注意，不要遗忘，因为标记已经下放到儿子节点了，不置为零的话就会重复}void update(int nl,int nr,int l,int r,int p,int k){//修改 nl~nr 的区间，当前在区间为 l~r 的节点上，节点标号为p，更新的值为k if(nl=r){//如果当前所到区间完全被包含在修改区间里，直接更新当前节点的标记 tag[p]+=k; ans[p]+=(r-l+1)*k; return ; } int mid=(l+r)>>1; push_down(p,l,r);//因为当前区间有不被包含的部分，所以先将之前的标记下放到左右儿子，再去找左右儿子 if(nl=mid+1)//如果右儿子有要被修改的部分 update(nl,nr,mid+1,r,rs(p),k);//修改右儿子 push_up(p); //合并左右儿子信息 return ;}

 

有几个注意的地方：

1.正确理解懒标记使用规则，当前节点懒标记下放后需置为0，换句话说，下放的规则为：将当前节点标记内容传到儿子结点，然后将当前节点的懒标记置为零。

2.若要修改的并不是整个当前节点，而是当前节点的若干个子节点，则必须要先下放当前节点的已存的懒标记，再去修改儿子结点。

3.update 函数参变量里的 nl，nr 为要修改的区间，在一次修改中自始至终是不变的。

小问题：之前我们说过了 push_up 函数要放在结尾，那为什么 push_down 函数要放在中间呢？

其实原理也很简单：push_up 函数是用来合并儿子结点信息的，所以自然要在儿子都改完的情况下再合并，而 push_down 函数是用来下传父亲信息的，自然要在儿子改之前就下传下去（辅助儿子的修改）。

3.区间查询操作

然后我们来到了线段树的最后：查询！（快要胜利啦！）

其实懂了区间修改之后，在看区间查询就很简单了，大体思路是一样的。

int query(int ql,int qr,int l,int r,int p){//ql,qr为要查询的区间 if(ql=r){ //如果当前所在区间在要查询的区间之内 ,就直接返回当前节点所记录的值 return ans[p]; } push_down(p,l,r); //同样先下传当前节点懒标记 int res=0;//临时变量，用来记录和 int mid=(l+r)>>1; if(ql=mid+1)//如果右儿子有要被查询的部分 res+=query(ql,qr,mid+1,r,rs(p));//查询右儿子，res加上右儿子的值 return res; //返回res }

注意点：

1.参变量里的ql，qr为要查询的区间，在一次查询中自始至终是不变的。

2.查询儿子结点之前同样要将父亲节点的懒标记下放。

最后来一发模板标程（区间和问题）：

#include#include#include#include#include#define MAXN 100001 using namespace std;int n,ans[MAXN*4],m,a[MAXN*2],tag[MAXN*4];int ls(int x){ return x1; f(ls(p),l,mid,tag[p]); f(rs(p),mid+1,r,tag[p]); tag[p]=0; return ;}void update(int nl,int nr,int l,int r,int p,int k){ if(nl=r){ ans[p]+=(r-l+1)*k; tag[p]+=k; return ; } int mid=(l+r)>>1; push_down(p,l,r); if(nlmid) update(nl,nr,mid+1,r,rs(p),k); push_up(p); return ;}int query(int q_x,int q_y,int l,int r,int p){ int res=0; if(q_x=r) return ans[p]; int mid=(l+r)>>1; push_down(p,l,r); if(q_xmid) res+=query(q_x,q_y,mid+1,r,rs(p)); return res;}int main(){ scanf("%d%d",&n,&m); for(int i=1;i