建设网站建站公司,天津做网站网页的公司,软件自学网官方网站,品牌建设的四条主线这个系列终于更新了(主要因为树状数组初步比较成功)
话不多说#xff0c;切入正题。
什么是线段树#xff1f;
线段树是一种支持单点修改区间查询(树状数组也行) and 区间修改单点查询(树状数组不行) and 区间修改区间查询(树状数组更不行)的高级数据结构#xff0c;相当…这个系列终于更新了(主要因为树状数组初步比较成功)
话不多说切入正题。
什么是线段树
线段树是一种支持单点修改区间查询(树状数组也行) and 区间修改单点查询(树状数组不行) and 区间修改区间查询(树状数组更不行)的高级数据结构相当于树状数组plus版。 ——该图片来自百度百科
建树
我们先来看看怎么建树。线段树其实就是一个二叉树每个人结点管辖一个区间。所以我们开始可以建树了。左孩子有孩子分别递归一下。
void build(int idx,int l,int r){tree[idx].ll;tree[idx].rr;if(lr){//如果这个节点是叶子节点tree[i].suma[l];return;}int mid(lr)1;build(idx*2,l,mid);//分别构造左子树和右子树build(idx*21,mid1,r);tree[idx].sumtree[idx*2].sumtree[idx*21].sum;
}
顺便多一嘴线段树一般开4倍空间(除非你动态开点)但下面也有提及。
单点修改 区间查询
→单点修改
这个不难直接向下递归就完事儿了。返回时按做就可以了。
void modify(int idx,int k,int x){if(tree[idx].ltree[idx].r){//找到了tree[idx].sumx;return;}if(ktree[idx*2].r)modify(idx*2,k,x);elsemodify(idx*21,k,x);tree[idx].sumtree[idx*2].sumtree[idx*21].sum;//返回更新return;
}
→区间查询
接下来我们看看如何区间查询。我们其实就找我们来看看哪些区间被目标区间包含了。所以从根节点开始往下递归如果当前结点是被要查询的区间包含了则返回这个结点的信息时间复杂度为。
int query(int idx,int l,int r){if(tree[i].ll tree[i].rr)//如果区间被包括在目标区间里面,直接返回return tree[i].sum;if(tree[i].rl || tree[i].lr)//八竿子打不着return 0;int res0;if(tree[idx*2].rl)resquery(idx*2,l,r);//左端点和目标区间有交集,搜左子树if(tree[idx*21].lr)resquery(idx*21,l,r);//搜右子树return res;
}区间修改 单点查询
区间修改的话就把这个区间加上一个k的标记 单点查询的时候就从上跑到下把沿路的标记加起来就好。
→区间修改
void modify(int idx,int l,int r,int k) {if(tree[idx].ll tree[idx].rr){tree[idx].tagk;return;}int mid(tree[idx].ltree[idx].r)1;if(lmid)modify(idx*2,l,r,k);if(rmid)modify(idx*21,l,r,k);
}
→单点查询
void query(int pos,int x){int restree[pos].tag;if(tree[pos].ltree[pos].r)return res;int mid(tree[pos].ltree[pos].r)1;if(xmid)query(pos1,x);else query(pos1|1,x);
}
到这你就可以去做洛谷P3368了。今天元宵节我就不给你们挖坑了(其实是懒)。
#include bits/stdc.h
using namespace std;
const int maxn500005;
int ans;
int a[maxn];
struct node{int l,r;int num;
}tr[maxn*4];//线段树开四倍空间
void build(int p,int l,int r){tr[p]{l,r,0};if(lr){tr[p].numa[l];return ;}int mid(lr)1;build(p1,l,mid);build(p1|1,mid1,r);
}
void modify(int p,int l,int r,int k){if(tr[p].ll tr[p].rr){tr[p].numk;return;}int mid(tr[p].ltr[p].r)1;if(lmid)modify(p1,l,r,k);if(rmid)modify(p1|1,l,r,k);
}
void query(int p,int x){anstr[p].num;if(tr[p].ltr[p].r)return;int mid(tr[p].ltr[p].r)1;if(xmid)query(p1,x);elsequery(p1|1,x);
}
int main(){int n,m;cinnm;for(int i1;in;i)cina[i];build(1,1,n);for(int i1;im;i){int op;cinop;if(op1){int x,y,k;cinxyk;modify(1,x,y,k);}else{ans0;int x;cinx;query(1,x);coutansendl;}}return 0
}
还是没忍住挖了一个坑你们自己找吧ψ(∇´)ψ
区间查询 区间修改(懒标记lazy tag)
读完这个你才能说你会线段树。
当然这个可以说是最难的一个part了。你可能会说把前面的代码直接拉来用不就结束了吗但用不了多久你就会发现这个想法非常智慧。
那老办法行不通了有什么新办法吗当然有它就是懒标记。懒标记是怎么个回事呢还是刚刚
那张图。
比如我们要给[1,5]每一个加一那么向下递归时可以先不直接操作而是将管辖那个区间的领导的值加上1*5。当然递归回去的时候不要忘记更新上面的结点。(不要问我为什么一定要这么干因为我也不知道)
先看一下修改的代码。
void modify(int idx,int l,int r,int k){if(tree[idx].rr tree[idx].ll){tree[idx].sumk*(tree[idx].r-tree[idx].l1);tree[idx].lazyk;//记录lazytagreturn;}push_down(idx);//向下传递if(tree[idx*2].rl)modify(idx*2,l,r,k);if(tree[idx*21].lr)modify(idx*21,l,r,k);tree[idx].sumtree[idx*2].sumtree[idx*21].sum;return;
}
这个是push_down的代码↓
void push_down(int idx){//清空lazytag if(tree[idx].lazy!0){tree[idx*2].lazytree[idx].lazy;tree[idx*21].lazytree[idx].lazy;int mid(tree[idx].ltree[idx].r)/2;tree[idx*2].sumtree[idx].lazy*(mid-tree[idx*2].l1);tree[idx*21].sumtree[idx].lazy*(tree[idx*21].r-mid);tree[idx].lazy0;//归零}return;
}
那查询呢一样。只要没有被完全包含在目标区间里就push_down下放懒标记。并让每个区间加上。
int query(int i,int l,int r){if(tree[i].ll tree[i].rr)return tree[i].sum;if(tree[i].rl || tree[i].lr)return 0;push_down(i);int res0;if(tree[i*2].rl)resquery(i*2,l,r);if(tree[i*21].lr)resquery(i*21,l,r);return res;
}
ok以上就是本期的全部内容。如果有什么问题请在评论区指正。我们下期再见
友情提醒:洛谷P3368的代码有问题请不要无脑Ctrl CCtrl V
