分类 主席树 下的文章

BZOJ 1901: Zju2112 Dynamic Rankings

Description给定一个含有n个数的序列a[1],a[2],a[3]……a[n],程序必须回答这样的询问:对于给定的i,j,k,在a[i],a[i+1],a[i+2]……a[j]中第k小的数是多少(1≤k≤j-i+1),并且,你可以改变一些a[i]的值,改变后,程序还能针对改变后的a继续回答上面的问题。Input第一行有两个正整数n(1≤n≤10000),m(1≤m≤10000)。分别表示序列的长度和指令的个数。第二行有n个数,表示a[1],a[2]……a[n],这些数都小于10^9。接下来的m行描述每条指令每行的格式是下面两种格式中的一种。 Q i j k 或者 C- 阅读剩余部分 -

主席树学习笔记

主席树就是可持久化线段树,可以随时访问任何一个历史版本的线段树,所有操作的时间复杂度和线段树完全一致,是 O(logn),空间变成了 O(nlogn),是一种十分优秀的数据结构。对于线段树来说,每次操作都只会更改 logn 个节点,我们可以单独把这些节点存下来,然后剩下的节点和前一个版本的线段树共用就可以了,这样对于 n 个操作就需要存储 nlogn 个节点,这样空间复杂度 O(nlogn) 就证明出来了。具体来说怎么和前一个版本的线段树共用节点从而降低空间占用呢?当我们修改了一个节点,那么他的左右孩子中肯定有一个需要修改,那么修改其中的一个孩子,而另一个孩子我们直接指向上- 阅读剩余部分 -