哈尔滨营销网站建设公司,漳州微网站建设,南阳seo招聘,小程序开发费用多少钱我似乎很少写这种算法博客可持久化线段树概念概念介绍#xff08;类比帮助理解#xff09;简单分析一下时间和空间复杂度#xff08;内容池#xff09;模板结构体变量建树模板单点修改模板单点查询模板区间修改模板#xff08;pushup#xff09;区间修改模板#xff08;…
我似乎很少写这种算法博客可持久化线段树概念概念介绍类比帮助理解简单分析一下时间和空间复杂度内容池模板结构体变量建树模板单点修改模板单点查询模板区间修改模板pushup区间修改模板比较特别区间查询模板入门题可持久化线段树题目简单题解代码实现我以这种字体提醒大家是类比概念的理解
可持久化线段树概念
概念介绍类比帮助理解
概念可持久化线段树也叫函数式线段树它的主体是线段树准确的说是很多棵线段树。线段树表示的区间是输入数据的整个权值域如果值域空间太大要先离散化可能出现的元素值压缩值域空间。 线段树存储的信息是权值维护不同区间的权值分布情况。 对于有n个元素的序列S构造出n棵线段树T[1…n]每棵树Ti储存序列的每一个前缀S[1…i]中每类数的出现个数即权值分布情况。 陈立杰、Seter、Fotile等人称这种以值域作为区间长度的线段树为权值线段树。因为每棵线段树Ti维护的是前缀S[1…i]中每类数的出现个数。
一句话概括每次修改线段树上的值都新建一棵树保证原来的线段树未被覆盖 给几张图片帮助认识 对于可持久化线段树的操作保证每一次的线段树都不要被覆盖 可能会想到每一次都copy一棵完整的新树然后再新树上进行更改 空间会变成(nm)(nm)(nm)显然是不允许的
其实我们发现每一次都最多只修改log(n)log(n)log(n)个节点走到了叶子节点 其余的节点没经过的都跟原来的线段树状态是一样的 那么我们就没有必要去新建一些多余的节点储存同样的内容 所以可持久化线段树的修改每一次都只新建需要更改的新点不动的就直接赋成原来的状态 这样就保证了每一个状态下的线段树都被保存下来了且未对其发生更改 我们可以类比抄作业 A同学做完了一份作业树的最初始状态 B同学就开始抄A发现这其中有几处错误 那么他就在这几个题目上面赶紧写下自己的正确答案新建线段树 然后其它一样的地方就直接链接A同学的答案先不急着把答案写下来只用链接地址不变在后面要用到的时候就直接找到A的答案地址抄就可以了
假设这个时候C又开始抄B的又发现B有一些错误 他就悄悄更改这几处的答案新建点 与B一样的就链接地址虽然链接的是B的地址但是B链接的是A的地址所以就相当于C直接链接了A的地址 以此类推。。。
可持久化就意味着老师检查作业查询之时能找到每一位同学各自的答案并且每位同学都很不要脸 发现了别人的错误都不告诉别人自己偷偷摸摸的改生成了自己新的一份答案
不然你想如果A发现自己有个错误改了的话所有的同学都要更改那一道题所以要按住A不让他更改自己的答案保证后面的答案顺利传下去
我jio得这个类比非常贴近生活实际浅显易懂啊相信很多亲故都已经明白了吧 简单分析一下时间和空间复杂度内容池
因为是新建的点并未对以前的先单数进行深度增加或多几个叶子结点 查询和更改都应该是与线段树一样的时间复杂度O(logN)O(logN)O(logN) m次操作就是O(MlogN)O(MlogN)O(MlogN)是肯定可以接受的 唯一蜜汁迷人的就是这个空间问题 建初始树的空间与普通线段树是不一样的 因为普通线段树是num1num1num1num1∣1num1|1num1∣1叶子结点也会生成多的空儿子 所以空间会变成4N4N4N而主席树就不一样了用了内存池再加上写法的原因 叶子结点是不会多生成空儿子的,空间自然就是2N2N2N尽管本蒟蒻还是按着4N4N4N在开 有m次操作就有MlogNMlogNMlogN个新点就会多这么多空间 线段树总空间也就是(2NMlogN)(2NMlogN)(2NMlogN)
不建议大家卡着点开可以尽可能的多开一些保证不MLE就ok
模板
学习任何算法都有一定的模板刚开始多半都是靠背打多了过后就自然而然就理解了 没办法 接下来的多数模板我们以找最大值为例对于不同的情况适当更改部分代码即可
结构体变量
#define MAXN 1000005
struct node {int l, r, Max;
//依情况而决定里面的变量是Max,Min,Sum...
}tree[MAXN 2];建树模板
我都是写的动态建树挺不错的推荐嘻嘻 这里要注意必须把每一层的节点编号提前存下来 不然回溯的时候cnt早已多加了很多这样我们就对不上了 作业乱了名字跟真实试卷会对不上
int build ( int l, int r ) {int t cnt;if ( l r ) {tree[t].l tree[t].r 0;tree[t].Max a[l];return t;}int mid ( l r ) 1;tree[t].l build ( l, mid );tree[t].r build ( mid 1, r );tree[t].Max max ( tree[tree[t].l].Max, tree[tree[t].r].Max );return t;
}单点修改模板
把p这个点修改为v发现这份作业的p题错了偷偷摸摸不告诉别人自己改
int update ( int num, int p, int v, int l, int r ) {int t cnt;if ( l r ) {tree[t].l tree[t].r 0;tree[t].Max v;return t;}int mid ( l r ) 1;if ( p mid ) {tree[t].l update ( tree[num].l, p, v, l ,mid );tree[t].r tree[num].r;}else {tree[t].r update ( tree[num].r, p, v, mid 1, r );tree[t].l tree[num].l;}tree[t].Max max ( tree[tree[t].l].Max, tree[tree[t].r].Max );return t;
}单点查询模板
假设我们要找p的值老师开始检查作业抽查到我们的p题答案马上找链接的答案
int query ( int p, int num, int l, int r ) {if ( l r )return tree[num].Max;int mid ( l r ) 1;if ( p mid )return query ( p, tree[num].l, l, mid );elsereturn query ( p, tree[num].r, mid 1, r );
}区间修改模板pushup
首先面对线段树的区间修改大多数人都会采取lazy主席树也同样适用 但不同的是各棵树是彼此独立的如果我们lazy下放对于i这个状态是对的 但有可能到j状态时的树是不能加上这个lazy的这个lazy并不是j打上去的 所以不下放我们就回溯上放回来即可 我们之前说了每个人都小贱小贱的只会改自己的答案但是我们有些题贴的是别人的链接无法帮助别人改答案就只能等着别人改了答案更新了链接自己这份才能跟着改这个链接链上了甩都甩不掉
void pushup ( int root,int len ) {tree[root].sum tree[tree[root].l].sum tree[tree[root].r].sum tree[tree[root].l].lazy * ( len - ( len 1 ) ) tree[tree[root].r].lazy * ( len 1 );
}int update ( int root, int l, int r, int L, int R, int val ) {int t cnt;tree[t].lazy tree[root].lazy;tree[t].l tree[root].l;tree[t].r tree[root].r;tree[t].sum tree[root].sum;if ( L l r R ) {tree[t].lazy tree[root].lazy val;return t;}int mid ( l r ) 1;if ( L mid )tree[t].l update ( tree[root].l, l, mid, L, R, val );if ( mid R )tree[t].r update ( tree[root].r, mid 1, r, L, R, val );pushup ( t, r - l 1 );return t;
}区间修改模板比较特别
就用求区间和为例吧 对于有些奇怪的题区间是不能pushup和pushdown的那么就要另辟蹊径代替lazy上下放
我们采取另一种手段来实现修改查询操作就是每次在区间直接对区间答案进行修改 然后如果被划分到刚刚好的区间的时候打上lazy即可。 保证了如果区间有lazy那么这整个区间一定是被完全覆盖的
对于一次的修改L,R,lazy的标记只存在与L,R之间划分到的整个区间, 并且所有不是整区间的区间答案在找区间经过的途中都整体增加了该有的值包括整区间 然后每次查询答案其答案的初始化都是当前区间的lazy值乘上其区间大小 因为如果当前区间有lazy那么一定是整体覆盖的并且查询和修改 要把目标区间进行划分这样我每次查询和修改都能维护出合理的答案
int update( int suf, int pre, int l, int r, int L, int R, int val ){suf cnt;tree[suf].sum tree[pre].sum;tree[suf].l tree[pre].l;tree[suf].r tree[pre].r;tree[suf].lazy tree[pre].lazy;tree[suf].sum 1ll * ( R - L 1 ) * val;if( L l r R ) {tree[suf].lazy val;return suf;}int mid ( l r ) 1;if( R mid ) //全部都在左儿子区间 tree[suf].l update ( tree[suf].l, tree[pre].l, l, mid, L, R, val );else if( mid L ) //全部都在右儿子区间 tree[suf].r update ( tree[suf].r, tree[pre].r, mid 1, r, L, R, val );else { //左右皆有 tree[suf].l update ( tree[suf].l, tree[pre].l, l, mid, L, R, val );tree[suf].r update ( tree[suf].r, tree[pre].r, mid 1, r, L, R, val );}return suf;
}区间查询模板
其实亲故们都知道区间查询也可以完成单点的无非就是多传一个不用的变量罢了 这里假设的是找[L,R][L,R][L,R]之间的最大值
int query ( int L, int R, int num, int l, int r ) {if ( L l r R )return tree[num].Max;int mid ( l r ) 1;int ans1 - INF, ans2 - INF;if ( L mid )ans1 query ( L, R, tree[num].l, l, mid );if ( mid R )ans2 query ( L, R, tree[num].r, mid 1, r );return max ( ans1, ans2 );
}说了这么多也该是期末学习成果的展示了 只有做题才能更好的掌握运用主席树模板
入门题可持久化线段树
题目
题目描述 为什么说本题是福利呢因为这是一道非常直白的可持久化线段树的练习题目的并不是虐人而是指导你入门可持久化数据结构。
线段树有个非常经典的应用是处理RMQ问题即区间最大/最小值询问问题。现在我们把这个问题可持久化一下:
Q k l r 查询数列在第k个版本时区间[l, r]上的最大值 M k p v 把数列在第k个版本时的第p个数修改为v并产生一个新的数列版本
最开始会给你一个数列作为第1个版本。每次M操作会导致产生一个新的版本。 修改操作可能会很多呢如果每次都记录一个新的数列空间和时间上都是令人无法承受的。 所以我们需要可持久化数据结构 对于最开始的版本1我们直接建立一颗线段树维护区间最大值。
修改操作呢我们发现修改只会涉及从线段树树根到目标点上一条树链上logn个节点而已其余的节点并不会受到影响。所以对于每次修改操作我们可以只重建修改涉及的节点即可。 需要查询第k个版本的最大值那就从第k个版本的树根开始像查询普通的线段树一样查询即可。 要计算好所需空间哦
输入格式 第一行两个整数N, Q。N是数列的长度Q表示询问数 第二行N个整数是这个数列 之后Q行每行以0或者1开头0表示查询操作Q1表示修改操作M 格式为 0 k l r 查询数列在第k个版本时区间[l, r]上的最大值 或者 1 k p v 把数列在第k个版本时的第p个数修改为v并产生一个新的数列版本
输出格式 对于每个M询问输出正确答案
样例 input 4 5 1 2 3 4 0 1 1 4 1 1 3 5 0 2 1 3 0 2 4 4 0 1 2 4 output 4 5 4 4 解释 序列版本1: 1 2 3 4 查询版本1的[1, 4]最大值为4 修改产生版本2: 1 2 5 4 查询版本2的[1, 3]最大值为5 查询版本1的[4, 4]最大值为4 查询版本1的[2, 4]最大值为4
数据范围与提示 N 10000 Q 100000 对于每次询问操作的版本号k保证合法区间[l, r]一定满足1 l r N
简单题解
说过了这道题是一个入门版题照着模板打就可以了 对于每一个更改线段树的操作我们找到操作途中所经过的点重新建点 不覆盖原来的线段树模样对于不变的我们就直接把原来树上的地址直接甩过去就可以了 记录下第i个操作的根节点每一个线段树都是不相互影响冲突的只是有可能会共用一些点罢了。
代码实现
#include cstdio
#include iostream
using namespace std;
#define MAXN 1000005
#define INF 0x7f7f7f7f
struct node {int l, r, Max;
}tree[MAXN 2];
int cnt, tot, n, q;
int a[MAXN / 10], root[MAXN 2];
int build ( int l, int r ) {int t cnt;if ( l r ) {tree[t].l tree[t].r 0;tree[t].Max a[l];return t;}int mid ( l r ) 1;tree[t].l build ( l, mid );tree[t].r build ( mid 1, r );tree[t].Max max ( tree[tree[t].l].Max, tree[tree[t].r].Max );return t;
}
int update ( int num, int p, int v, int l, int r ) {int t cnt;if ( l r ) {tree[t].l tree[t].r 0;tree[t].Max v;return t;}int mid ( l r ) 1;if ( p mid ) {tree[t].l update ( tree[num].l, p, v, l ,mid );tree[t].r tree[num].r;}else {tree[t].r update ( tree[num].r, p, v, mid 1, r );tree[t].l tree[num].l;}tree[t].Max max ( tree[tree[t].l].Max, tree[tree[t].r].Max );return t;
}
int query ( int L, int R, int num, int l, int r ) {if ( L l r R )return tree[num].Max;int mid ( l r ) 1;int ans1 - INF, ans2 - INF;if ( L mid )ans1 query ( L, R, tree[num].l, l, mid );if ( mid R )ans2 query ( L, R, tree[num].r, mid 1, r );return max ( ans1, ans2 );
}
int main() {scanf ( %d %d, n, q );for ( int i 1;i n;i )scanf ( %d, a[i] );root[ tot] build ( 1, n );for ( int i 1;i q;i ) {int opt, k, p, v;scanf ( %d %d %d %d, opt, k, p, v );if ( opt 0 )printf ( %d\n, query ( p, v, root[k], 1, n ) );elseroot[ tot] update ( root[k], p, v, 1, n );}return 0;
}相信这篇博客会帮助大家更好地理解可持久化线段树如果有错误的地方欢迎大家指出改正谢谢联系方式139红酒白酒葡萄酒评论 ヾ(ToT)ByeBye 讲得好的话点个赞亲(づ3)づ╭❤
