NOIp 2018 前的数据结构板子总结

发表于 更新于 分类于
NOIp范围内的数据结构

Disjoint-set data structure

通过路径压缩实现最常用的并查集

题目链接: Luogu P3367 【模板】并查集

时间复杂度: 1. MakeSet: \(\Theta(n)\) 2. Find: \(\Theta(\alpha(n))\) 3. Union: \(\Theta(\alpha(n))\) (\(\alpha(n)\)为inverse Ackermann function)

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
#include <cstdio>
int parent[10010];
int n, m, opt, u, v;
inline void MakeSet(const int &maximum) {
  for (register int i(0); i <= maximum; ++i) {
    parent[i] = i;
  }
}
inline int Find(const int &cur) {
  return cur == parent[cur] ? cur : parent[cur] = Find(parent[cur]);
}
inline void Union(const int &x, const int &y) {
  parent[Find(y)] = Find(x);
}
int main(int argc, char const *argv[]) {
  scanf("%d %d", &n, &m);
  MakeSet(n);
  while (m--) {
    scanf("%d %d %d", &opt, &u, &v);
    switch (opt) {
      case 1: {
        Union(u, v);
        break;
      }
      case 2: {
        puts(Find(u) == Find(v) ? "Y" : "N");
        break;
      }
    }
  }
  return 0;
}

Heap

由于C++中包含用堆实现的priority_queue, 就不手写了。

题目链接: Luogu P3378 【模板】堆

时间复杂度: 1. top: \(\Theta(1)\) 2. pop: \(\Theta(\lg n)\) 3. push: \(\Theta(\lg 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
#include <queue>
#include <cstdio>
std::priority_queue<int, std::vector<int>, std::greater<int> > Q;
int n, opt, x;
int main(int argc, char const *argv[]) {
  scanf("%d", &n);
  while (n--) {
    scanf("%d", &opt);
    switch (opt) {
      case 1: {
        scanf("%d", &x);
        Q.push(x);
        break;
      }
      case 2: {
        printf("%d\n", Q.top());
        break;
      }
      case 3: {
        Q.pop();
        break;
      }
    }
  }
  return 0;
}

Fenwick tree

也叫binary indexed tree

时间复杂度: 1. LOWBIT: \(\Theta(1)\) 2. Sum: \(\Theta(\lg n)\) 3. Add: \(\Theta(\lg n)\)

单点修改 + 区间查询

题目链接: Luogu P3374 【模板】树状数组 1

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
#include <cstdio>
#define LOWBIT(a) (a & -a)
int fenwick_tree[500010], n;
inline int Sum(register int index) {
  register int ret(0);
  while (index) {
    ret += fenwick_tree[index],
    index -= LOWBIT(index);
  }
  return ret;
}
inline void Add(register int index, const int &kDelta) {
  while (index <= n) {
    fenwick_tree[index] += kDelta,
    index += LOWBIT(index);
  }
}
#undef LOWBIT
int m, opt, x, y;
int main(int argc, char const *argv[]) {
  scanf("%d %d", &n, &m);
  for (register int i(1); i <= n; ++i) {
    scanf("%d", &y),
    Add(i, y);
  }
  while (m--) {
    scanf("%d %d %d", &opt, &x, &y);
    switch (opt) {
      case 1: {
        Add(x, y);
        break;
      }
      case 2: {
        printf("%d\n", Sum(y) - Sum(x - 1));
        break;
      }
    }
  }
  return 0;
}

区间修改 + 单点查询

原树状数组的基础上使用差分。

题目链接: Luogu P3368 【模板】树状数组 2

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
#include <cstdio>
#define LOWBIT(a) (a & -a)
int fenwick_tree[500010], n;
inline int Sum(register int index) {
  register int ret(0);
  while (index) {
    ret += fenwick_tree[index],
    index -= LOWBIT(index);
  }
  return ret;
}
inline void Add(register int index, const int &kDelta) {
  while (index <= n) {
    fenwick_tree[index] += kDelta,
    index += LOWBIT(index);
  }
}
#undef LOWBIT
int m, opt, x, y, k;
int main(int argc, char const *argv[]) {
  scanf("%d %d", &n, &m);
  for (register int i(1); i <= n; ++i) {
    scanf("%d", &y),
    Add(i, y - x),
    x = y;
  }
  while (m--) {
    scanf("%d %d", &opt, &x);
    switch (opt) {
      case 1: {
        scanf("%d %d", &y, &k);
        Add(x, k), Add(y + 1, -k);
        break;
      }
      case 2: {
        printf("%d\n", Sum(x));
        break;
      }
    }
  }
  return 0;
}

区间修改 + 区间查询

仍然使用了差分, 推导过程如下:

设原数组为\(a_n\), 考虑一个差分数组\(b_n = a_n - a_{n - 1}\)(约定\(b_0 = 0\)), 可以得到

\[ \begin {aligned} \sum_{i = 1}^n a_i &= \sum_{i = 1}^n \sum_{j = 1}^i b_i \\\\ &= \sum_{i = 1}^{n - i + 1} b_i \\\\ &= \sum_{i = 1}^n (n + 1 - i)b_i \\\\ &= (n + 1)\sum_{i = 1}^n b_i - \sum_{i = 1}^n ib_i \end {aligned} \]

写的简单易懂就是

\[ \begin{aligned} &a_1 + a_2 + \cdots + a_{n - 1} + a_n \\\\ = &b_1 + (b_1 + b_2) + \cdots + (b_1 + b_2 + \cdots + b_{n - 2} + b_{n - 1}) + (b_1 + b_2 + \cdots + b_{n - 1} + b_n)\\\\ = &nb_1 + (n - 1)b_2 + \cdots + 2b_{n - 1} + b_n\\\\ = &(n + 1 - 1)b_1 + (n + 1 - 2)b_2 + \cdots + [n + 1 - (n - 1)]b_{n - 1} + (n + 1 - n)b_n\\\\ = &(n + 1)(b_1 + b_2 + \cdots + b_{n - 1} + b_n) - (b_1 + 2b_2 + \cdots + (n - 1)b_{n - 1} + nb_n) \end{aligned} \]

把\(b_i\)和\(ib_i\)分别用两个树状数组维护就可以了。

题目链接: Luogu P3372 【模板】线段树 1

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
#include <cstdio>
#define LOWBIT(a) (a & -a)
long long fenwick_tree1[100010], fenwick_tree2[100010];
int n;
inline long long Sum(const long long *fenwick_tree, register int index) {
  register long long ret(0ll);
  while (index) {
    ret += fenwick_tree[index],
    index -= LOWBIT(index);
  }
  return ret;
}
inline void Add(register long long *fenwick_tree, register int index, const long long &kDelta) {
  while (index <= n) {
    fenwick_tree[index] += kDelta,
    index += LOWBIT(index);
  }
}
#undef LOWBIT
int m, opt;
long long x, y, k;
int main(int argc, char const *argv[]) {
  scanf("%d %d", &n, &m);
  for (register int i(1); i <= n; ++i) {
    scanf("%lld", &y);
    Add(fenwick_tree1, i, y - x), Add(fenwick_tree2, i, i * (y - x));
    x = y;
  }
  while (m--) {
    scanf("%d %lld %lld", &opt, &x, &y);
    switch (opt) {
      case 1: {
        scanf("%lld", &k);
        Add(fenwick_tree1, x, k), Add(fenwick_tree1, y + 1, -k),
        Add(fenwick_tree2, x, x * k), Add(fenwick_tree2, y + 1, (y + 1) * -k);
        break;
      }
      case 2: {
        printf("%lld\n", (y + 1) * Sum(fenwick_tree1, y) - x * Sum(fenwick_tree1, x - 1) - (Sum(fenwick_tree2, y) - Sum(fenwick_tree2, x - 1)));
        break;
      }
    }
  }
  return 0;
}

Segment tree

只放一个板子题吧, 记住框架就行。

时间复杂度: 1. Construct: \(\Theta(n \lg n)\) 2. Update: \(\Theta(1)\) 3. PushDown: \(\Theta(1)\) 4. Sum: \(\Omega(\lg n)\) 5. Query: \(\Omega(\lg n)\)

题目链接: Luogu P3372 【模板】线段树 1

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
#include <cstdio>
struct SegmentTree {
  long long value, delta;
  int l, r;
  SegmentTree *left, *right;
  SegmentTree(const long long &val = 0) {
    value = val, delta = 0;
    left = right = nullptr;
    l = r = 0;
  }
  inline void Update() {
    this->value = (this->left ? this->left->value : 0ll) + (this->right ? this->right->value : 0ll);
  }
  inline void PushDown() {
    if (this->delta && this->left) {
      this->left->value += (this->left->r - this->left->l + 1) * this->delta,
      this->right->value += (this->right->r - this->right->l + 1) * this->delta;
      this->left->delta += this->delta,
      this->right->delta += this->delta;
      this->delta = 0ll;
    }
  }
  SegmentTree(const int &le, const int &ri) {
    this->l = le, this->r = ri;
    this->left = this->right = nullptr;
    this->delta = 0ll;
    if (le == ri) {
      scanf("%lld", &this->value);
    } else {
      register int mid((le + ri) >> 1);
      this->left = new SegmentTree(le, mid);
      this->right = new SegmentTree(mid + 1, ri);
      this->Update();
    }
  }
  ~SegmentTree() {
    if (left) {
      delete left;
      delete right;
    }
  }
  inline long long Query(const int &le, const int &ri) {
    if (le <= this->l && this->r <= ri) {
      return this->value;
    } else {
      this->PushDown();
      register int mid((this->l + this->r) >> 1);
      return (le <= mid ? this->left->Query(le, ri) : 0ll) + (mid < ri ? this->right->Query(le, ri) : 0ll);
    }
  }
  inline void Add(const int &le, const int &ri, const long long &kDelta) {
    if (le <= this->l && this->r <= ri) {
      this->value += (this->r - this->l + 1) * kDelta,
      this->delta += kDelta;
    } else {
      this->PushDown();
      register int mid((this->l + this->r) >> 1);
      if (le <= mid) {
        this->left->Add(le, ri, kDelta);
      }
      if (mid < ri) {
        this->right->Add(le, ri, kDelta);
      }
      this->Update();
    }
  }
} *root;
int n, m, opt, x, y;
long long k;
int main(int argc, char const *argv[]) {
  scanf("%d %d", &n, &m);
  root = new SegmentTree(1, n);
  while (m--) {
    scanf("%d %d %d", &opt, &x, &y);
    switch (opt) {
      case 1: {
        scanf("%lld", &k);
        root->Add(x, y, k);
        break;
      }
      case 2: {
        printf("%lld\n", root->Query(x, y));
        break;
      }
    }
  }
  return 0;
}

Heavy path decomposition

别人都放在图论里, 就我一个放在数据结构里。

推荐博客: 树链剖分详解

题目链接: Luogu P3384 【模板】树链剖分

时间复杂度: 1. Dfs1: \(\Theta(n)\) 2. Dfs2: \(\Theta(n)\) 3. PathModify: \(\Omega(\lg n)\) 4. PathGetSum: \(\Omega(\lg n)\) 5. SubTreeModify: \(\Omega(\lg n)\) 6. SubTreeGetSum: \(\Omega(\lg 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
147
148
149
150
151
152
153
154
155
#include <cstdio>
#include <vector>
#include <algorithm>
struct Node {
  long long value, delta;
  Node *left, *right;
  int l, r;
  Node() {
    left = right = nullptr;
    l = r = delta = value = 0;
  }
  ~Node() {
    if (left) {
      delete left;
      delete right;
    }
  }
} *root;
std::vector<int> adj[100010];
int heavy[100010], size[100010], father[100010], top[100010], depth[100010];
int new_index[100010];
long long original_value[100010], indexed_value[100010];
int maxtop, n, m;
long long kMod;
void Dfs1(const int &cur, const int &fathernode) {
  father[cur] = fathernode,
  depth[cur] = depth[fathernode] + 1,
  size[cur] = 1;
  for (auto i : adj[cur]) {
    if (i != fathernode) {
      Dfs1(i, cur),
      size[cur] += size[i];
      if (size[i] > size[heavy[cur]]) heavy[cur] = i;
    }
  }
}
void Dfs2(const int &cur, const int &topnode) {
  static int index_count(0);
  new_index[cur] = ++index_count,
  indexed_value[index_count] = original_value[cur];
  top[cur] = topnode;
  if (heavy[cur]) {
    Dfs2(heavy[cur], topnode);
    for (auto i : adj[cur]) {
      if (i != father[cur] && i != heavy[cur]) {
        Dfs2(i, i);
      }
    }
  }
}
#define PUSH_UP(cur) cur->value = cur->left->value + cur->right->value;
void Build(Node *cur, const int &l, const int &r) {
  if (l == r) {
    cur->value = indexed_value[l];
    cur->l = cur->r = l;
  } else {
    cur->left = new Node, cur->right = new Node;
    register int mid((l + r) >> 1);
    cur->l = l, cur->r = r;
    Build(cur->left, l, mid), Build(cur->right, mid + 1, r);
    PUSH_UP(cur);
  }
}
#define PUSH_DOWN(cur) if (cur->delta) {cur->left->value = (cur->left->value + cur->delta * (cur->left->r - cur->left->l + 1)) % kMod, cur->right->value = (cur->right->value + cur->delta * (cur->right->r - cur->right->l + 1)) % kMod, cur->left->delta = (cur->left->delta + cur->delta) % kMod, cur->right->delta = (cur->right->delta + cur->delta) % kMod, cur->delta = 0;}
void Modify(Node *cur, const int &l, const int &r, const long long &kDelta) {
  if (l <= cur->l && cur->r <= r) {
    cur->value += kDelta* ((cur->r - cur->l) + 1),
    cur->delta += kDelta;
  } else {
    PUSH_DOWN(cur);
    register int mid((cur->l + cur->r) >> 1);
    if (l <= mid) Modify(cur->left, l, r, kDelta);
    if (mid < r) Modify(cur->right, l, r, kDelta);
    PUSH_UP(cur);
  }
}
long long GetSum(Node *cur, const int &l, const int &r) {
  if (l <= cur->l && cur->r <= r) {
    return cur->value;
  } else {
    PUSH_DOWN(cur);
    register long long ret(0);
    register int mid((cur->l + cur->r) >> 1);
    if (l <= mid) (ret += GetSum(cur->left, l, r)) %= kMod;
    if (mid < r) (ret += GetSum(cur->right, l, r)) %= kMod;
    return ret % kMod;
  }
}
inline void PathModify(const int &x, const int &y, const long long &kDelta) {
  register int a(x), b(y);
  while (top[a] != top[b]) {
    if (depth[top[a]] < depth[top[b]]) std::swap(a, b);
    Modify(root, new_index[top[a]], new_index[a], kDelta);
    a = father[top[a]];
  }
  if (depth[a] > depth[b]) std::swap(a, b);
  Modify(root, new_index[a], new_index[b], kDelta);
}
inline long long PathGetSum(const int &x, const int &y) {
  register int a(x), b(y);
  register long long ret(0ll);
  while (top[a] != top[b]) {
    if (depth[top[a]] < depth[top[b]]) std::swap(a, b);
    (ret += GetSum(root, new_index[top[a]], new_index[a])) %= kMod;
    a = father[top[a]];
  }
  if (depth[a] > depth[b]) std::swap(a, b);
  return (ret + GetSum(root, new_index[a], new_index[b])) % kMod;
}
inline void SubTreeModify(const int &x, const long long &kDelta) {
  Modify(root, new_index[x], new_index[x] + size[x] - 1, kDelta);
}
inline long long SubTreeGetSum(const int &x) {
  return GetSum(root, new_index[x], new_index[x] + size[x] - 1);
}
int main(int argc, char const *argv[]) {
  scanf("%d %d %d %lld", &n, &m, &maxtop, &kMod);
  for (int i(1); i <= n; ++i) scanf("%lld", &original_value[i]);
  for (int i(1), u, v; i < n; ++i) {
    scanf("%d %d", &u, &v),
    adj[u].push_back(v),
    adj[v].push_back(u);
  }
  Dfs1(maxtop, maxtop), Dfs2(maxtop, maxtop),
  root = new Node,
  Build(root, 1, n);
  long long z;
  register int opt, x, y;
  while (m--) {
    scanf("%d", &opt);
    switch (opt) {
      case 1: {
        scanf("%d %d %lld", &x, &y, &z),
        PathModify(x, y, z % kMod);
        break;
      }
      case 2: {
        scanf("%d %d", &x, &y),
        printf("%lld\n", PathGetSum(x, y));
        break;
      }
      case 3: {
        scanf("%d %lld", &x, &z),
        SubTreeModify(x, z % kMod);
        break;
      }
      case 4: {
        scanf("%d", &x),
        printf("%lld\n", SubTreeGetSum(x));
        break;
      }
    }
  }
  return 0;
}