权值线段树(值域线段树)

权值线段树(值域线段树)

在我看来权值线段树不是一种线段树的变种,它是指用线段树来维护权值的一种思想,因此并没有太大难度

权值线段树可以用于解决静态区间第k大问题

我们通过例题来了解权值线段树


例题

A.求逆序对对数

在以往的版本中,我们求逆序对可以使用树状数组实现,显然使用树状数组实现的功能均可以使用线段树来实现,只不过线段树的空间和常数要大一些。

如果没有学习过求逆序对的方法,建议先去学习再来看这道题

回忆如何使用树状数组来求逆序对数,我们给序列内元素记录它们在原序列中的名次(即下标),然后按照它们的值进行递增排序,按照排序后的顺序从第一个开始依次处理。处理一个元素的过程:查询在这个元素之前被处理的名次小于当前元素名次的元素个数,然后在树状数组当前元素名次处加1,即我们用树状数组维护已经处理的元素的按照名次作为下标的出现次数。

那么我们很容易得就可以将这个问题移植到线段树上,只需使线段树维护的底层数组下标代表元素未排序前的名次,线段树的数值维护在对应名次元素出现次数,然后查询前缀和就是查询[1,\space rank_{i}]区间的数值

这样就是一个最最简单的权值线段树了,权值在这里指的是元素出现的次数

当然如果想要更好理解,我们可以这样处理,名次定义为这些元素在排好序以后的名次,然后做一个元素-名次的映射,然后按照原序列顺序处理,处理过程:每次统计名次比当前名次大的元素个数,即查询后缀(对于树状数组:或者一开始倒着排序,查询前缀,或者按照原顺序倒着处理,查询前缀) 这样似乎更加符合正常认知

B.BZOJ_4627

简述题意

给出一个全局 LR,给你一个整数序列,问你序列中和值在 [L,\space R] 中的子串有多少个。

模型转换

利用序列前缀和我们有 当 i < j 时,求所有 L<=sum_{j}-sum_{i}<=Rij 数对对数((i,j)(j,i)算同一对),我们把式子移项,设当前下标为j,我们有sum_{j}-R<=sum_{i}<=sum_{j}-L,显而易见,我们只需要统计在第j个数之前且在[sum_{j}-R,\space sum_{j}-L] 内的i的个数即可。

因此我们可以用权值线段树来解决这道题,我们用线段树维护值域内sum值出现的次数,但是值域十分大,是[-1e10,1e10],我们用传统
的初始把点建全的线段树必然不能解决问题,这时我们有两种方法(我只知道这两种):数据离散化或者线段树的动态开点,离散化方法有很多局限性,比如需要离线,离散化耗时难写(假的),那么我们来讲一下动态开点

线段树动态开点

动态开点,既对于一些我们在整个程序中都不会用到的点,我们就不为它们分配内存空间,而对于用得到的点我们只开根节点到这个叶子节点的链上的节点,从而达到节省内存的效果。动态开点空间复杂度分析:线段树树高为logNN为值域,那么我们插入n次,即nlogN

回到这道题,我们的线段树节点内存池大小应当开1e5 * log(2e10),代码如下

#include <iostream>
#include <cstdio>


typedef long long LL;


inline LL read() {
    LL x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}


const LL INF = 10000000007; //1e5 * 1e5
const int MAXN = 100007;


struct Segment_Tree {
    struct Node {
        int sum;
        Node *ls, *rs;

        inline void push_up() {
            sum = 0;
            if (ls != NULL) {
                sum += ls->sum;
            }
            if (rs != NULL) {
                sum += rs->sum;
            }
            return;
        }
    } node[MAXN * 35];
    int cnt;
    Node* root;
    inline void init() {
        cnt = 0;
        root = newNode();
    }
    inline Node* newNode() {
        return &node[++cnt];
    }
    inline void insert(Node* &cur, LL pos, LL l, LL r) {
        if (cur == NULL) {
            cur = newNode();
        }

        if (l == r) {
            ++cur->sum;
            return;
        }
        else {
            LL mid = (l + r) >> 1;
            if (pos <= mid) {
                insert(cur->ls, pos, l, mid);
            }
            else {
                insert(cur->rs, pos, mid + 1, r);
            }
        }
        cur->push_up();
        return;
    }
    inline int query(Node* &cur, LL x, LL y, LL l, LL r) {
        if (cur == NULL) {
            return 0;
        }
        if (x <= l && r <= y) {
            return cur->sum;
        }
        LL mid = (l + r) >> 1;
        int res = 0;
        if (x <= mid) res += query(cur->ls, x, y, l, mid);
        if (y > mid) res += query(cur->rs, x, y, mid + 1, r);
        return res;
    }
}tree;


int main() {
    LL n = read(), L = read(), R = read(), sum = 0;
    tree.init();
    tree.insert(tree.root, 0, -INF, INF);
    LL ans = 0;
    for (LL i = 1; i <= n; ++i) {
        sum += read();
        ans += tree.query(tree.root, sum - R, sum - L, -INF, INF);
//std::cout << "query:: " << sum - R << " " << sum - L << " " << ans << std::endl;
        tree.insert(tree.root, sum, -INF, INF);
//std::cout << "insert:: " << sum << std::endl;
    } 
    std::cout << ans;
    return 0;
}

C.Hard

给出一个序列,问你当前序列中排名为k的数是什么,同时我们会不断向序列尾部加入新的元素,询问夹杂在插入中,元素范围已知

这个问题是权值线段树进化为主席树的跳板,请务必弄懂

考虑暴力:每次插入就排序(当然不能使用快排,根据性质要用 O(n) 的),回答询问,但显然复杂度爆炸,即单次 O(n) 维护, O(1) 查询

考虑权值线段树解法:

我们模仿前两题做法,权值线段树维护每个数字出现次数,动态开点实现,然后把它当作” 数字搜索树 “,我们用和平衡树查询第k大数字相同的方法。

查询左子树节点个数 x ,若 x < k 在右子树递归查找,同时 k-=x 因为随着递归深入查询左子节点的权值和不再是查询整个序列前缀,而是每个小区间的前缀;(你也可以这样理解:我们递归到右子树的时候查询的应该,前面有 x 个元素前提下,查询当前块内第 k – x 个元素是什么)

x>=k 我们在左子树递归查找,但是 k 不变,因为我们和上一次查询的是同一个前缀。

这个小问题就解决了

发表评论

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