树状数组套权值线段树

静态区间 k 小值（POJ 2104 K-th Number） 的问题可以用 权值线段树 在 的时间复杂度内解决。

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

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

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

优化的思路是把二分答案的操作和查询小于一个值的数的数量两种操作结合起来，使用 线段树套动态开点权值线段树，由于所有线段树的结构是相同的，可以在多棵树上同时进行线段树上二分。

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

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

由于线段树的常数较大，在实现中往往使用常数更小且更方便处理前缀和的 树状数组 实现。另外空间复杂度是 的，使用时 注意空间限制。

给出一种代码实现：

实现 
  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
147
148
149
150
151
152
153
154
155
156
157
158
159
160
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <map>
#include <set>
#define LC o << 1
#define RC o << 1 | 1
using namespace std;
constexpr 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;

// 树状数组实现
namepace fenwick_impl {
  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);
    }
  }
}
using namespace fenwick_impl;

// 线段树实现
namespace segtree_impl {
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);
  }
}
}  // namespace segtree_impl

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;
}
本页面最近更新：2024/10/9 22:38:42，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：Enter-tainer, GavinZhengOI, H-J-Granger, hsfzLZH1, Ir1d, ouuan, sshwy, countercurrent-time, Great-designer, ksyx, NachtgeistW, renbaoshuo, SukkaW, Tiphereth-A, xyf007
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用