建设企业网站初始必备的六大功能,梧州市建设局官方网站,dw asp access 网站开发优点,做冻品的网站可持久化线段树
模板
在某一指定版本的单点查#xff0c;单点修。
开 m m m 棵线段树#xff0c;每次修改复制后单点修。时间复杂度 O ( m ( n log n ) ) O(m(n\log n)) O(m(nlogn))#xff0c;空间复杂度 O ( n m ) O(nm) O(nm)#xff0c;不如暴力。
每次修改…可持久化线段树
模板
在某一指定版本的单点查单点修。
开 m m m 棵线段树每次修改复制后单点修。时间复杂度 O ( m ( n log n ) ) O(m(n\log n)) O(m(nlogn))空间复杂度 O ( n m ) O(nm) O(nm)不如暴力。
每次修改的时候影响的点是 log n \log n logn 级的其余点均不受影响。因修改而新建线段树时可以利用未修改的点做到 O ( m log n ) O(m \log n) O(mlogn)。
具体实现动态开点即可空间复杂度 O ( m log n n ) O(m \log nn) O(mlognn)注意线段树自身的常数。
代码
静态 kth
模板
第 l − 1 , r l-1,r l−1,r 棵线段树形态相同可以相减得到区间答案。
离散化二分答案每次统计区间内小于他的个数。这个过程可以用可持久化线段树实现时间复杂度 O ( m log 2 n ) O(m \log ^2n) O(mlog2n)。
事实上这个过程可以做到 O ( m log n ) O(m \log n) O(mlogn)。即查询时记左子树区间的数量为 L L L。 L ≥ k L \ge k L≥k则在左子树中继续找第 k k k 大否则右子树找第 k − L k - L k−L 大。
