树状数组套主席树

静态区间 k 小值 (POJ 2104 K-th Number) 的问题可以用 主席树 在 O(n\log n) 的时间复杂度内解决。

如果区间变成动态的呢？即，如果还要求支持一种操作：单点修改某一位上的值，又该怎么办呢？

例题二逼平衡树（树套树）
例题ZOJ 2112 Dynamic Rankings

如果用 线段树套平衡树 中所论述的，用线段树套平衡树，即对于线段树的每一个节点，对于其所表示的区间维护一个平衡树，然后用二分来查找 k 小值。由于每次查询操作都要覆盖多个区间，即有多个节点，但是平衡树并不能多个值一起查找，所以时间复杂度是 O(n\log^3 n) ，并不是最优的。

思路是，把二分答案的操作和查询小于一个值的数的数量两种操作结合起来。最好的方法是使用 线段树套主席树 。

说是主席树其实不准确，因为并不是对线段树的可持久化，各个线段树之间也没有像主席树各版本之间的强关联性，所以称为 动态开点权值线段树 更为确切。

思路类似于线段树套平衡树，即对于线段树所维护的每个区间，建立一个动态开点权值线段树，表示其所维护的区间的值。

在修改操作进行时，先在线段树上从上往下跳到被修改的点，删除所经过的点所指向的动态开点权值线段树上的原来的值，然后插入新的值，要经过 O(\log n) 个线段树上的节点，在动态开点权值线段树上一次修改操作是 O(\log n) 的，所以修改操作的时间复杂度为 O(\log^2 n) 。

在查询答案时，先取出该区间覆盖在线段树上的所有点，然后用类似于静态区间 k 小值的方法，将这些点一起向左儿子或向右儿子跳。如果所有这些点左儿子存储的值大于等于 k ，则往左跳，否则往右跳。由于最多只能覆盖 O(\log n) 个节点，所以最多一次只有这么多个节点向下跳，时间复杂度为 O(\log^2 n) 。

由于线段树的常数较大，在实现中往往使用常数更小且更方便处理前缀和的 树状数组 实现。

给出一种代码实现：

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <map>
#include <set>
#define LC o << 1
#define RC o << 1 | 1
using namespace std;
const int maxn = 1000010;
int n, m, a[maxn], u[maxn], x[maxn], l[maxn], r[maxn], k[maxn], cur, cur1, cur2,
    q1[maxn], q2[maxn], v[maxn];
char op[maxn];
set<int> ST;
map<int, int> mp;
struct segment_tree  //封装的动态开点权值线段树
{
  int cur, rt[maxn * 4], sum[maxn * 60], lc[maxn * 60], rc[maxn * 60];
  void build(int& o) { o = ++cur; }
  void print(int o, int l, int r) {
    if (!o) return;
    if (l == r && sum[o]) printf("%d ", l);
    int mid = (l + r) >> 1;
    print(lc[o], l, mid);
    print(rc[o], mid + 1, r);
  }
  void update(int& o, int l, int r, int x, int v) {
    if (!o) o = ++cur;
    sum[o] += v;
    if (l == r) return;
    int mid = (l + r) >> 1;
    if (x <= mid)
      update(lc[o], l, mid, x, v);
    else
      update(rc[o], mid + 1, r, x, v);
  }
} st;
//树状数组实现
inline int lowbit(int o) { return (o & (-o)); }
void upd(int o, int x, int v) {
  for (; o <= n; o += lowbit(o)) st.update(st.rt[o], 1, n, x, v);
}
void gtv(int o, int* A, int& p) {
  p = 0;
  for (; o; o -= lowbit(o)) A[++p] = st.rt[o];
}
int qry(int l, int r, int k) {
  if (l == r) return l;
  int mid = (l + r) >> 1, siz = 0;
  for (int i = 1; i <= cur1; i++) siz += st.sum[st.lc[q1[i]]];
  for (int i = 1; i <= cur2; i++) siz -= st.sum[st.lc[q2[i]]];
  // printf("j %d %d %d %d\n",cur1,cur2,siz,k);
  if (siz >= k) {
    for (int i = 1; i <= cur1; i++) q1[i] = st.lc[q1[i]];
    for (int i = 1; i <= cur2; i++) q2[i] = st.lc[q2[i]];
    return qry(l, mid, k);
  } else {
    for (int i = 1; i <= cur1; i++) q1[i] = st.rc[q1[i]];
    for (int i = 1; i <= cur2; i++) q2[i] = st.rc[q2[i]];
    return qry(mid + 1, r, k - siz);
  }
}
/*
线段树实现
void build(int o,int l,int r)
{
    st.build(st.rt[o]);
    if(l==r)return;
    int mid=(l+r)>>1;
    build(LC,l,mid);
    build(RC,mid+1,r);
}
void print(int o,int l,int r)
{
    printf("%d %d:",l,r);
    st.print(st.rt[o],1,n);
    printf("\n");
    if(l==r)return;
    int mid=(l+r)>>1;
    print(LC,l,mid);
    print(RC,mid+1,r);
}
void update(int o,int l,int r,int q,int x,int v)
{
    st.update(st.rt[o],1,n,x,v);
    if(l==r)return;
    int mid=(l+r)>>1;
    if(q<=mid)update(LC,l,mid,q,x,v);
    else update(RC,mid+1,r,q,x,v);
}
void getval(int o,int l,int r,int ql,int qr)
{
    if(l>qr||r<ql)return;
    if(ql<=l&&r<=qr){q[++cur]=st.rt[o];return;}
    int mid=(l+r)>>1;
    getval(LC,l,mid,ql,qr);
    getval(RC,mid+1,r,ql,qr);
}
int query(int l,int r,int k)
{
    if(l==r)return l;
    int mid=(l+r)>>1,siz=0;
    for(int i=1;i<=cur;i++)siz+=st.sum[st.lc[q[i]]];
    if(siz>=k)
    {
        for(int i=1;i<=cur;i++)q[i]=st.lc[q[i]];
        return query(l,mid,k);
    }
    else
    {
        for(int i=1;i<=cur;i++)q[i]=st.rc[q[i]];
        return query(mid+1,r,k-siz);
    }
}
*/
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) scanf("%d", a + i), ST.insert(a[i]);
  for (int i = 1; i <= m; i++) {
    scanf(" %c", op + i);
    if (op[i] == 'C')
      scanf("%d%d", u + i, x + i), ST.insert(x[i]);
    else
      scanf("%d%d%d", l + i, r + i, k + i);
  }
  for (set<int>::iterator it = ST.begin(); it != ST.end(); it++)
    mp[*it] = ++cur, v[cur] = *it;
  for (int i = 1; i <= n; i++) a[i] = mp[a[i]];
  for (int i = 1; i <= m; i++)
    if (op[i] == 'C') x[i] = mp[x[i]];
  n += m;
  // build(1,1,n);
  for (int i = 1; i <= n; i++) upd(i, a[i], 1);
  // print(1,1,n);
  for (int i = 1; i <= m; i++) {
    if (op[i] == 'C') {
      upd(u[i], a[u[i]], -1);
      upd(u[i], x[i], 1);
      a[u[i]] = x[i];
    } else {
      gtv(r[i], q1, cur1);
      gtv(l[i] - 1, q2, cur2);
      printf("%d\n", v[qry(1, n, k[i])]);
    }
  }
  return 0;
}
build本页面最近更新：，更新历史
edit发现错误？想一起完善？ 在 GitHub 上编辑此页！
people本页面贡献者：OI-wiki
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用

评论