权值线段树模板 / p1908

---

前言

权值线段树是解决区间出现个数的一个好工具

其实现结构与普通线段树无太大区别，所不同的是权值线段树所维护的是元素出现个数

此外还要加一个离散化防止数组越界

权值线段树支持以下功能：

全局查询第 k 大 \ 小，查询区间元素出现个数、单点更新、查询单点元素出现个数

模板里有前三者的功能函数，对于第四功能，可利用第二功能稍加修改即可

一、 例题

题目链接 洛谷p1908

二、 思路及代码

1. 思路

很经典的权值线段树例题，问题是求逆序对

我们知道 $$ans=\sum _{i=1}^n\sum _{j=i+1}^n[a_i>aj]$$
用权值线段树统计${\sum }_{j=i+1}^n[a_i>aj]$是一件很容易的事情，

于是我们对query累加即可得到答案

注意：求逆序对时，离散化不需要去重

2. 代码

代码如下 ：

#include <algorithm>
#include <iostream>
#define int long long
using namespace std;
const int maxn = 5e5 + 5;
struct vtree {
  int l, r;
  int v;
} t[maxn << 2];
int n;
int a[maxn], b[maxn];
void build(int root, int l, int r) {
  t[root].l = l, t[root].r = r, t[root].v = 0;
  if (l == r) return;
  int mid = (l + r) >> 1;
  build(root * 2, l, mid);
  build(root * 2 + 1, mid + 1, r);
}
void update(int root, int k) {  // 权值线段树仅支持单点更新
  if (t[root].l == t[root].r) {
    if (t[root].l == k) t[root].v++;
    return;
  }
  int mid = (t[root].r + t[root].l) >> 1;
  if (k <= mid) update(root * 2, k);
  if (mid < k) update(root * 2 + 1, k);
  t[root].v = t[root * 2].v + t[root * 2 + 1].v;
}
int query(int root, int l, int r) {  // 区间元素个数
  if (l <= t[root].l && t[root].r <= r) return t[root].v;
  int ans = 0;
  int mid = (t[root].l + t[root].r) >> 1;
  if (l <= mid) ans += query(root * 2, l, r);
  if (mid < r) ans += query(root * 2 + 1, l, r);
  return ans;
}
int query_kth(int root, int k) {  // 区间第k小的元素
  if (t[root].l == t[root].r) return t[root].l;
  int left = t[root * 2].v;
  if (k <= t[root * 2].v)
    return query_kth(root * 2, k);
  else
    return query_kth(root * 2 + 1, k - left);
}
void dispersed() {
  for (int i = 1; i <= n; i++) b[i] = a[i];  // 权值线段树离散化
  sort(b + 1, b + n + 1);                    // 求逆序对不必去重
  for (int i = 1; i <= n; i++) a[i] = lower_bound(b + 1, b + n + 1, a[i]) - b;
}
signed main() {
  //   freopen("in.txt", "r", stdin);
  //   freopen("out.txt", "w", stdout);
  int ans = 0;
  scanf("%lld", &n);
  for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
  build(1, 1, n);
  dispersed();
  for (int i = 1; i <= n; i++) {
    ans += query(1, a[i] + 1, n);  // 求所有编号比自己大，值比自己小的数的个数
    update(1, a[i]);
  }
  printf("%lld\n", ans);
}
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