目录
题目
http://poj.org/problem?id=3264
题目大意：给出一个序列，求
[a, b]
的最大值与最小值之差。
分析
线段树裸题。单点更新，区间查询。
线段树内存储区间内的最大值与最小值，查询时使用
pair<int, int>
返回。
代码
// 2748K 2954MS
#include <iostream>
#include <cstdio>
#include <cstring>
#include <utility>
const int INF = 0x3f3f3f3f;
const int N = 200100, STSIZE = 4 * N;
using namespace std;
struct Node {
int l, r, x, y; //x -> min; y -> max
} st[STSIZE]; //Enough
void init(int i, int l, int r) {
st[i].l = l;
st[i].r = r;
st[i].x = INF;
st[i].y = -INF;
if (l >= r) return;
int m = l + r >> 1;
init(2 * i, l, m);
init(2 * i + 1, m + 1, r);
}
int update(int i, int x, int v) {
if (st[i].l == st[i].r) {
st[i].x = st[i].y = v;
} else {
int m = st[i].l + st[i].r >> 1;
if (x <= m) update(2 * i, x, v);
if (x > m) update(2 * i + 1, x, v);
st[i].x = min(st[2 * i].x, st[2 * i + 1].x);
st[i].y = max(st[2 * i].y, st[2 * i + 1].y);
}
}
pair<int, int> select(int i, int l, int r) {
if (l <= st[i].l && st[i].r <= r) {
return make_pair(st[i].x, st[i].y);
} else {
pair<int, int> a, b;
a = b = make_pair(INF, -INF);
int m = st[i].l + st[i].r >> 1;
if (l <= m) {
a = select(2 * i, l, r);
}
if (r > m ) {
b = select(2 * i + 1, l, r);
}
return make_pair(min(a.first, b.first), max(a.second, b.second));
}
}
int main() {
pair<int, int> p;
for (int n, q, v, a, b, x, y; ~scanf("%d%d", &n, &q);) {
init(1, 1, n);
for (int i = 1; i <= n; i++) {
scanf("%d", &v);
update(1, i, v);
}
for (int i = 0; i < q; i++) {
scanf("%d%d", &a, &b);
p = select(1, a, b);
cout << p.second - p.first << endl;
}
}
return 0;
}
关于线段树长度的思考
之前一直没有仔细考虑过这个问题，现在仔细来思考一下。
对于一个长度为
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)
。
实现
单点增/改，区间查询如下。
区间改暂时不在本文中提及。（区间改看起来有点麻烦，调试起来也没有传统递归版本直观，感觉优势不大）
代码
//2384K 3047MS
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 220000, INF = 0x3f3f3f3f;
int M, d[N], e[N];
void build(int n) {
memset(d, 0, sizeof(d));
memset(e, 0, sizeof(e));
for (M = 1; M < n; M <<= 1); //找到大于 n 的2的次幂 M
for (int i = M + 1, t; i <= M + n; i++) {
scanf("%d", &t);
d[i] = e[i] = t;
}
for (int i = M - 1; i; i--) { //执行一次对全体父节点的更新
d[i] = max(d[i << 1], d[i << 1 | 1]);
e[i] = min(e[i << 1], e[i << 1 | 1]);
}
}
// When increase by y, it is
// for (d[x += M] += y, x >>= 1; x; x >>= 1)
int query(int s, int t) {
int x = -INF, y = INF;
for (s += M - 1, t += M + 1; s ^ t ^ 1; s >>= 1, t >>= 1) {
if (~s & 1) { //为左儿子
x = max(x, d[s ^ 1]);
y = min(y, e[s ^ 1]);
}
if (t & 1) { //为右儿子
x = max(x, d[t ^ 1]);
y = min(y, e[t ^ 1]);
}
}
return x - y;
}
// l^r^1 左边的这个点和右边这个点是否互为兄弟，或者就是同一个点
// ~l&1 判断这个节点是否为左儿子
// r&1 判断这个节点是否为右儿子
int main() {
for (int n, m, a, b; ~scanf("%d%d", &n, &m);) {
build(n);
while (m--) {
scanf("%d%d", &a, &b);
printf("%d\n", query(a, b));
}
}
return 0;
}
补充此题中没有出现的初始化后修改方法：
void update(int x, int y) {
for (d[x += bit] = y, x >>= 1; x; x >>= 1)
d[x] = max(d[x << 1], d[x << 1 | 1]);
// P.S. 只算了最大值
}
参考资料
- 传统线段树空间占用4*n的证明
https://blog.csdn.net/gl486546/article/details/78243098 - zkw线段树
https://blog.csdn.net/keshuqi/article/details/52205884 - zkw线段树
https://www.cnblogs.com/frankchenfu/p/7132445.html - 递归实现的zkw线段树，写法比较特别
https://blog.csdn.net/qwb492859377/article/details/51410438
本作品使用基于以下许可授权：Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.