题目

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. 只算了最大值
}

 

参考资料

  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.

发表评论

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