| 线段树，从入门到入坑 | 您所在的位置：网站首页 › 区间与值域 › 线段树，从入门到入坑 |
线段树，从入门到入坑
|
推荐在个人博客上阅读。 前言线段树，是数据结构皇冠上的明珠（我编的）。 它用途广泛，被一代代的oier应用，改进，优化。 本文介绍了线段树的基础知识和各种拓展（包括权值线段树，可持久化线段树），各种优化方式（包括zkw线段树，动态开点，离散化），希望能帮到更多的oier。 在学习线段树前，默认你应该学会一下内容： 树和二叉树的基本知识（这你总得会吧） 二叉堆（主要是堆式储存） 离散化（其实并不需要） 会写代码如果你不会，左转oiwiki，如果你会，那么继续读吧！ 线段树的引入举个例子，我们现在有一个序列，想维护一段子区间的和，该怎么办呢？ 你或许会说，可以暴力！把这个区间的数加起来就行了。 那么如果这个子区间里有1e5个数呢？ 前缀和？ 如果强制在线呢？ 如果在维护区间和的同时维护最大值、并且支持区间修改呢？ 我们有很多种办法维护区间问题，比如树状数组，线段树，分块。其中，线段树是较通用且直观的一种数据结构。 基础线段树 线段树入门首先，我们有一个序列。 $$\left \{ 1,1,4,5,1,4 \right \} $$ 我们利用二分的思想，用每一个节点表示一个区间，两个子节点表示左右两个子区间。
注意：实际上，只有最下面一层的叶子节点才保存了实际的数字，其它的每个节点只保存着这个区间的信息（如区间和，区间最值等） 那么如何把子节点的信息传到父节点上呢？ 我们要了解一个叫做$pushup$的操作。 void pushup(int x){ tr[x].sum=tr[x*2].sum+tr[x*2+1].sum; }这个操作的意思就是：节点表示的区间和等于两个子节点所表示的区间之和。即下图：
事实上，还有另一种写法的线段树，不需要建树，但是需要$O( n\log n)$的时间复杂度插入数据，我们会在权值线段树部分介绍这种写法。 建树代码 void build(int x,int l,int r){ tr[x].l=l,tr[x].r=r;//节点表示区间的左右界 if(l==r){ //若l=r，说明这个节点是叶子节点，直接赋值 tr[x].sum=a[l];//a是原数列 return; } int mid=(l+r)/2;//mid表示左右子区间的间隔 build(x*2,l,mid),build(x*2+1,mid+1,r);//递归建树 //线段树是完全二叉树，左右子节点可以用x*2,x*2+1表示 tr[x].sum=tr[x*2].sum+tr[x*2+1].sum;//pushup操作 } 区间查询线段树可以在$O(\log n)$的时间复杂度下完成区间查询操作。 以刚刚的数列$\left \{ 1,1,4,5,1,4 \right \}$为例。 此时如果询问$[3,5]$之间的区间和，我们该怎么办呢？
查询$[4,5]$怎么办呢？ 可以把$[4,6]$拆成$[4,5]$和$[6,6]$，然后输出$[4,5]$的和。 那么$[3,5]$就可以表示为$[3,3]$和$[4,5]$。
区间查询代码 int query(int x,int l,int r){ //区间查询 if(tr[x].l>=l&&tr[x].r>q; for(int i=1;i>a[i]; build(1,1,n);//建树 while(q--){ int t,b,c; cin>>t>>b>>c; if(t==1) change(1,b,c); else coutq; for(int i=1;i>a[i]; build(1,1,n); while(q--){ int l,r,k,c; cin>>c>>l>>r; if(c==1){ cin>>k; update(1,l,r,k); } else coutm>>p; for(int i=1;i>a[i]; build(1,1,n); while(m--){ cin>>ch>>t>>g; if(ch==1){ cin>>c; change(1,t,g,0,c); } else if(ch==2){ cin>>c; change(1,t,g,c,1); } else cout>m; coutp; insert(1,1,n,m,p); } else{ //下车 cin>>m>>p; insert(1,1,n,m,-p); } } } 查询第k大数请注意，这个查询第k大是针对整个权值线段树的，要查区间第k大请去学主席树或树套树。 权值线段树是维护值域的，一个节点的左右端点都应该是一个具体的数字，而且值域肯定是递增的，所以我们可以二分。 如果 $k$小于区间中点，那么也就说明结果为左区间第$k$大数。否则，也就说明结果为右区间第$k−l_{size}$大数。 代码 int kth(int x,int l,int r,int k){ if(l==r) return l;//查到了，返回即可 int mid=(l+r)/2; if(k>x; switch(opt){ case 1: insert(1,-N,N,x,1);//插入 break; case 2: insert(1,-N,N,x,-1);//删除 break; case 3: cout |
然后我们就可以在每个节点处维护一些信息。
有了这个操作，我们就可以递归的求出每一个节点所表示的信息。
这个建立线段树的过程可以看作是预处理信息，把数组的信息转移到线段树的叶子节点上，时间复杂度大概是$O(n)$
首先，如果直接查询$[4,6]$的区间和，我们肯定是会的，直接输出10就行。
所以无论我们查询多大的区间，都可以拆成一些（不超过$\log n$）预处理过的子区间，把这些子区间的区间和加起来，就是答案。【本文地址】