【数据结构】线段树（入门）

【数据结构】线段树（入门）

一.原理：

1.结构： 完全二叉树（不懂的点这个呀：​​传送门​​​）2.可以维护的内容： sum,max,min等

struct node{ int l,r;//左右端点 int sum,maxx,minn;//要维护的值}

3.示意图（直接盗用学长课件里的图啦）

线段树的每个节点表示一个区间，子节点则分别表示父节点的左右半区间，例如父亲的区间是[a,b]，那么(c=(a+b)/2)左儿子的区间是[a,c]，右儿子的区间是[c+1,b]。（来自课件）

（其实这个的原理跟模拟堆差不多，那篇博客被我鸽了 ）

4.说明：

区间[l,r]一般分为[l,mid],[mid+1,r];mid=floor(l+r>>1);//下取整

二.基本操作：

1.建树（递归）2.单点修改：3.区间查询： （1）、如果这个区间被完全包括在目标区间里面，直接返回这个区间的值

（2）、如果这个区间的左儿子和目标区间有交集，那么递归左儿子

（3）、如果这个区间的右儿子和目标区间有交集，那么递归右儿子

三.代码：

1.pushup：用子节点更新当前节点信息

void pushup(int u){ tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;}

2.build: 在一段区间上初始化线段树

void build(int u,int l,int r){ if(l==r){ tr[u].l=l;tr[u].r=r;tr[u].sum=w[r]; } else{ tr[u].l=l;tr[u].r=r; int mid=l+r >> 1; build(u << 1,l,mid);build(u<<1|1,mid+1,r); pushup(u); }}

3.update：单点修改

void update(int u,int x,int v){ if(tr[u].l==tr[u].r) tr[u].sum+=v; else{ int mid=tr[u].l+tr[u].r >> 1; if(x<=mid) update(u<<1,x,v); else update(u<<1|1,x,v); pushup(u); }}

4.query：区间查询

int query(int u,int l,int r){ if(tr[u].l>=l&&tr[u].r<=r) return tr[u].sum; int mid=tr[u].l+tr[u].r >> 1; int sum=0; if(l<=mid) sum=query(u<<1,l,r); if(r>mid) sum+=query(u<<1|1,l,r); return sum;}

四.模板题

原题链接：​​传送门​​​（更好的阅读体验） （洛谷上也有几道模板题的 可以去做）

题目描述 给定 n 个数组成的一个数列，规定有两种操作，一是修改某个元素，二是求子数列 [a,b] 的连续和。

输入格式 第一行包含两个整数 n 和 m，分别表示数的个数和操作次数。

第二行包含 n 个整数，表示完整数列。

接下来 m 行，每行包含三个整数 k,a,b （k=0，表示求子数列[a,b]的和；k=1，表示第 a 个数加 b）。

数列从 1 开始计数。

输出格式 输出若干行数字，表示 k=0 时，对应的子数列 [a,b] 的连续和。

数据范围 1≤n≤100000, 1≤m≤100000， 1≤a≤b≤n输入样例： 10 5 1 2 3 4 5 6 7 8 9 10 1 1 5 0 1 3 0 4 8 1 7 5 0 4 8输出样例： 11 30 35线段树解法：

#includeusing namespace std;const int maxn=1e5+10;int n,m,w[maxn];struct node{ int l,r,sum;}tr[4*maxn];void pushup(int u){ tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;}void build(int u,int l,int r){ if(l==r){ tr[u].l=l;tr[u].r=r;tr[u].sum=w[r]; } else{ tr[u].l=l;tr[u].r=r; int mid=l+r >> 1; build(u << 1,l,mid);build(u<<1|1,mid+1,r); pushup(u); }}int query(int u,int l,int r){ if(tr[u].l>=l&&tr[u].r<=r) return tr[u].sum; int mid=tr[u].l+tr[u].r >> 1; int sum=0; if(l<=mid) sum=query(u<<1,l,r); if(r>mid) sum+=query(u<<1|1,l,r); return sum;}void update(int u,int x,int v){ if(tr[u].l==tr[u].r) tr[u].sum+=v; else{ int mid=tr[u].l+tr[u].r >> 1; if(x<=mid) update(u<<1,x,v); else update(u<<1|1,x,v); pushup(u); }}int main(){ cin>>n>>m; for(int i=1;i<=n;i++) cin>>w[i]; build(1,1,n); int op,x,y; while(m--){ cin>>op>>x>>y; if(!op) printf("%d\n",query(1,x,y)); else update(1,x,y); } return 0;}

树状数组解法：

#includeusing namespace std;const int N = 1e5+6;int tr[N];int a[N];int n,m;int lowbit (int x){ return x&(-x);} void add(int x,int y){ for(int i=x;i<=n;i+=lowbit(i)) tr[i]+=y;}int sum(int x){ int res=0; for(int i=x;i>0;i-=lowbit(i)) res+=tr[i]; return res;}int main(){ cin>>n>>m; for(int i=1;i<=n;i++){ cin>>a[i]; add(i,a[i]); } while(m--){ int k,x,y; cin>>k>>x>>y; if(k==0) cout<

五：进阶-区间修改

为了实现这个，引入一个新的状态——懒标记。

作用：存储到这个节点的修改信息，暂时不把修改信息传到子节点。

实现思路：

递归到这个节点时，只更新这个节点的状态，并把当前的更改值累积到标记中。

下传操作

①当前节点的懒标记累积到子节点的懒标记中。

②修改子节点状态。在引例中，就是原状态+子节点区间点的个数*父节点传下来的懒标记。

③父节点懒标记清0。

比较好的几篇博客呀：

​​线段树从零开始​​​​线段树详解 （原理，实现与应用）​​

​​线段树 从入门到进阶​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。