Hellc

本文主要讨论用 树状数组套权值线段树 解决 带修改的区间排名 的问题。

问题

给定序列，要求支持以下操作：

• 给定区间 $[l, r)$，求该区间内排名为 $k$ 的元素
• 修改某一位上的数

首先声明

如果没有修改的话，可以用主席树解决，参阅 主席树 - 学习笔记。

在网上的很多文章，虽然写着用 树状数组套主席树 解决，然而他们讲的和写的，根本不是什么 树状数组套主席树 ，而是 树状数组套权值线段树 ，跟主席树没有关系，跟可持久化也没有关系！！！

如果非要用到主席树，可以用对原序列建主席树，然后用树状数组套权值线段树维护增量，可是我不觉得这有什么意义啦。

所以以下说的和主席树没有关系。

关于权值线段树，也可以参阅上面那篇文章。

思路

就是一个树套树的通常思路，外层树状数组维护前缀，内层权值线段树求排名为 $k$ 的元素。

对比一般的树状数组来理解，如果说一般的树状数组维护的是某个前缀内元素的和，那么这里的树状数组维护的就是某个前缀内元素构成的权值线段树，原来是把 $O(\log n)$ 个区间的和加起来，现在就是把 $O(\log n)$ 个区间的权值线段树加起来，原来的修改会影响树状数组上 $O(\log n)$ 个区间的和，现在的修改就是在 $O(\log n)$ 颗权值线段树中插入元素。

所以我们可以用树状数组求出前缀的权值线段树，然后将两个前缀树相减，即可得到所需区间的权值线段树，这里和用主席树解决静态问题时的做法类似。

时间复杂度修改和查询都是 $O(\log n\log w)$ 的，空间复杂度是 $O(m\log n\log w)$ 的。

例题

BZOJ 1901 Dynamic Rankings

模板题。

因为我这种存孩子指针和区间线段树的写法空间较大，所以实现上还要注意一些空间问题。

主要措施一个是把动态开点的左右分开，另一个是在不需要往下走，但需要其信息的，直接写成空的信息（本题中即 cnt = 0），而不需要开点。

#include <cstdio>
#include <vector>
#include <algorithm>
#include <climits>
  
const int MAXN = 10000;
const int MAXW = 1e9;
  
struct SegmentTree{
    SegmentTree *lc, *rc;
    int l, r;
    int cnt;
 
    SegmentTree(int l = 0, int r = 0) : l(l), r(r), lc(NULL), rc(NULL), cnt(0) {
        ;
    }
 
    void pushDownL();
    void pushDownR();
    void update();
    void insert(int x, int delta);
};
 
void SegmentTree::pushDownL(){
    if(!lc){
        lc = new SegmentTree(l,  l + (r - l >> 1));
    }
}
 
void SegmentTree::pushDownR(){
    if(!rc){
        rc = new SegmentTree(l + (r - l >> 1), r);
    }
}
 
void SegmentTree::update(){
    cnt = (lc ? lc->cnt : 0) + (rc ? rc->cnt : 0);
}
 
void SegmentTree::insert(int x, int delta){
    if(r - l == 1){
        cnt += delta;
    } else{
        int mid = l + (r - l >> 1);
        if(x < mid) pushDownL(), lc->insert(x, delta); else pushDownR(), rc->insert(x, delta);
        update();
    }
}
 
struct PresentTree{
    int a[MAXN + 1];
    int n;
    SegmentTree *T[MAXN + 1];
    std::vector<SegmentTree*> L, R; // b - a
 
    int lowbit(signed int x){
        return x & -x;
    }
 
    int query(int k){
        int l = T[0]->l, r = T[0]->r;
        while(r - l != 1){
            int cnt = 0;
            for(int i = 0; i < L.size(); i++) cnt -= L[i]->lc ? L[i]->lc->cnt : 0;
            for(int i = 0; i < R.size(); i++) cnt += R[i]->lc ? R[i]->lc->cnt : 0;
  
            int mid = l + (r - l >> 1);
            if(k <= cnt){
                r = mid;
                for(int i = 0; i < L.size(); i++) L[i]->pushDownL(), L[i] = L[i]->lc;
                for(int i = 0; i < R.size(); i++) R[i]->pushDownL(), R[i] = R[i]->lc;
            } else{
                l = mid;
                for(int i = 0; i < L.size(); i++) L[i]->pushDownR(), L[i] = L[i]->rc;
                for(int i = 0; i < R.size(); i++) R[i]->pushDownR(), R[i] = R[i]->rc;
                k -= cnt;
            }
        }
        return l;
    }
 
    int query(int l, int r, int k){ // (l, r]
        L.clear(), R.clear();
        for(int i = l; i; i -= lowbit(i)) L.push_back(T[i]);
        for(int i = r; i; i -= lowbit(i)) R.push_back(T[i]);
        return query(k);
    }
 
    void modify(int i, int x){
        int &old = a[i];
        for(; i <= n; i += lowbit(i)){
            T[i]->insert(old, -1);
            T[i]->insert(x, 1);
        }
        old = x;
    }
 
    void build(){
        for(int i = 0; i <= n; i++) T[i] = new SegmentTree(0, MAXW + 1);
        for(int i = 1; i <= n; i++){
            for(int k = i; k <= n; k += lowbit(k)){
                T[k]->insert(a[i], 1);
            }
        }
    }
} solver;
 
int main(){
    int m;
    scanf("%d%d", &solver.n, &m);
    for(int i = 1; i <= solver.n; i++) scanf("%d", solver.a + i);
 
    solver.build();
 
    for(int i = 0; i < m; i++){
        char opt;
        do opt = getchar(); while(opt != 'C' && opt != 'Q');
 
        if(opt == 'Q'){
            int l, r, k;
            scanf("%d%d%d", &l, &r, &k);
            printf("%d\n", solver.query(l - 1, r, k));
        } else if(opt == 'C'){
            int pos, x;
            scanf("%d%d", &pos, &x);
            solver.modify(pos, x);
        } else throw;
    }
     
    return 0;
}

就是这样啦