SS's Trace

Sirius's Blog

POJ 3264 - USACO - 线段树 - zkw线段树

题目

http://poj.org/problem?id=3264

题目大意:给出一个序列,求 [a, b] 的最大值与最小值之差。

分析

线段树裸题。单点更新,区间查询。
线段树内存储区间内的最大值与最小值,查询时使用 pair<int, int> 返回。

代码

关于线段树长度的思考

之前一直没有仔细考虑过这个问题,现在仔细来思考一下。

对于一个长度为 N 的区间,其对应的线段树一定有 2*N-1个节点。(易证)

所以如果使用链式存储的话,将会使用 2*N-1的存储空间;但如果使用数组模拟的话,最坏的情况需要使用 4*N的存储空间,因为未加优化的化线段树可能不是一棵完全二叉树。

我自己的一种想法是尽量构建一棵完全二叉树,来节省空间。这种做法还是基于传统递归版本线段树,只是做了少许空间优化。

如对于长度为 10 的区间构建线段树,采用对半分的方法会拆分成 [1,5][6,10]两个区间。此时 [3,3] , [4,5] 均没有子节点,空间存在浪费。如果以 [1,6] , [7,10] 的划分方法则可以构建一棵完全二叉树。

第二种操作就是使用 zkw线段树。对于一棵完全二叉树,不难想到对于任何一棵完全二叉树,每一个节点(即线段树上的一个区间)的位置都是可以计算出来,唯一确定的。此时可以用一段连续的空间来存储线段树上的数据。再暴力一点,我们可以构建一个[1, M]区间上的线段树( M=2^k, k∈N, M >= n ),使其为一棵满二叉树,所有子节点存储在节点数为 M 的最后一层,浪费的空间不要了,反正也不多。

zkw线段树

概述

一种写起来比较短比较省空间的线段树。

有人说效率也会高,我暂时还没有感觉到相对传统递归版本有什么效率上的提高。

zkw线段树的单点查询时间复杂度为 O(1) 。

实现

单点增/改,区间查询如下。

区间改暂时不在本文中提及。(区间改看起来有点麻烦,调试起来也没有传统递归版本直观,感觉优势不大)

代码

补充此题中没有出现的初始化后修改方法:

 

参考资料

  1. 传统线段树空间占用4*n的证明
    https://blog.csdn.net/gl486546/article/details/78243098
  2. zkw线段树
    https://blog.csdn.net/keshuqi/article/details/52205884
  3. zkw线段树
    https://www.cnblogs.com/frankchenfu/p/7132445.html
  4. 递归实现的zkw线段树,写法比较特别
    https://blog.csdn.net/qwb492859377/article/details/51410438

CC BY-NC-SA 4.0 本作品使用基于以下许可授权:Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注