【NOIp复习】数据结构之线段树

线段树

会用到的公式：将完全二叉树从左到右、从上到下依次编号，设当前结点编号为n左节点编号为：2*n 右节点编号为2*n+1把空节点的编号初始化为-1 线段树的本质其实是二叉搜索树啦，所以说可以很方便的解决区间最大最小、查询区间和、修改区间和的问题用数组表示线段树的话，如果本身的区间长度为n，线段树节点数2*n左右，开3*n的大小很保险设线段树上节点代表区间为[a,b]，那么左子树代表[a,(a+b)/2]，右子树代表[(a+b)/2,b]如果a==b，那么该节点为叶子结点，否则递归建树

先写了个很难看的代码…（并不能作为模板，模板在后面）

#include <cstdio> #include <cstring> #include <algorithm> #include <iostream> #define maxn 50010 #define REP(a,b) for(int i=a;i<=b;i++) using namespace std; struct node{ int left,right,val;//左右端点（代表该节点覆盖线段范围）、权值 }tree[maxn*3]; int s[maxn];//这里的s是读入的待建树数组 int ans=0;//查询的区间和累加在ans上，注意每次查询之后都要重置ans为0 void create(int l, int r, int num){//建树操作，左右端点与节点编号作为传入参数 tree[num].left=l; tree[num].right=r; if(l==r) { tree[num].val=s[l]; return; } else { create(l,(l+r)/2,num*2); create((l+r)/2+1,r,num*2+1); tree[num].val=tree[num*2].val+tree[num*2+1].val;//这里以维护区间和为例 return; } } void add(int a, int b, int num){//第a个位置增加b，当前修改节点编号为num tree[num].val+=b; if(tree[num].left==tree[num].right) return;//已经修改到叶子了，不必再向下修改 else{ if(a>(tree[num].left+tree[num].right)/2) add(a,b,num*2+1);//如果a在num节点的右区间，访问右子树 else add(a,b,num*2); return; } } void ask(int l, int r, int num){//查询从l到r的区间和，当前考察节点编号为num if(l<=tree[num].left&&r>=tree[num].right){//如果该节点存放的是待查找区间的一部分，就可以把这个节点累加上去而不必再往下搜索了 ans+=tree[num].val; return; } if(l>tree[num].right||r<tree[num].left) return; else{ int mid=(tree[num].left+tree[num].right)/2; if(l>mid) { ask(l,r,num*2+1); return; } else if(r<mid) { ask(l,r,num*2); return; } else { ask(l,r,num*2); ask(l,r,num*2+1); return; } return; } }

线段树的区间修改（lazy思想）

首先是改进了上一段代码的表示方法，不将num节点所存储的区间端点放在结构体中，而是放在函数中作为参数传入，可以用macro简化代码。【代码中的大写字母L,R都代表num节点的左右端点，小写字母l,r代表查询或修改区间的左右端点】 其次是用pushDown函数和lazy标记实现了区间修改，因为区间修改没有必要在查询到它之前去向下传递，在修改时只需要检查当前num节点是否有lazy，如果有，pushDown之后看修改区间在什么位置对左右子树进行递归操作。查询和修改几乎完全一样。

#include <cstdio> #include <cstring> #define maxn 100000+10 #define lson L,mid,rt<<1 //左子树 左端点，右端点，编号 #define rson mid+1,R,rt<<1|1 #define root L,R,rt struct node{ int val, lazy; }T[maxn<<2]; void pushUp(int num){//num节点的左右子树都已经更新完毕了再pushUp更新num本身 T[num].val=T[num<<1].val+T[num<<1|1].val; } void pushDown(int L,int R,int num){ int mid=(L+R)>>1; T[num<<1].val=T[num].lazy*(mid-L+1); T[num<<1|1].val=T[num].lazy*(R-mid); T[num<<1].lazy=T[num].lazy; T[num<<1|1].lazy=T[num].lazy; T[num].lazy=0; } void build(int L,int R,int num){ if(L==R){ scanf("%d",&T[num].val); return; //如果数组s[i]是已经读入的数据的话 //T[num].val=s[L]; return; } int mid=(L+R)>>1; build(lson); build(rson); pushUp(num);//左右子树都计算完成了就可以把自己算出来啦 } void update(int l,int r,int v,int L,int R,int rt){ //在覆盖[L,R]的rt节点的[l,r]区间增加v if(l==L&&r==R){ T[rt].lazy=v; T[rt].val=v*(R-L+1); return; } int mid=(L+R)>>1; if(T[rt].lazy) pushDown(root); if(r<=mid) update(l,r,v,lson);//注意向下取整左取等右不取等 else if(l>mid) update(l,r,v,rson); else{ update(l,mid,v,lson); update(mid+1,r,v,rson); } pushUp(num); } int query(int l,int r,int L,int R,int rt){ if(l==L&&r==R) return T[rt].val; int mid=(L+R)>>1; if(T[rt].lazy) pushDown(root); if(r<=mid) return query(l,r,lson); else if(l>mid) return query(l,r,rson); return query(l,mid,lson)+query(mid+1,r,rson); } int main(){ int n,q; scanf("%d",&n); build(1,n,1);//从根节点开始建树 scanf("%d",&q); while(q--){ //应对多组查询 } return 0; }

练习题

HDU 1166 单点修改，区间查询，用树状数组也可以实现 HDU 1754 查询区间最大值 HDU 1698 区间修改，区间查询，lazy思想 HDU 1394 求逆序数，也可以用树状数组，记录每个位置与左边的差 POJ 2777 位运算，区间修改

转载于:https://www.cnblogs.com/leotan0321/p/6081369.html