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

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)

#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)$

#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

#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

#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

#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

#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)$

可以换用树状数组, 常数更小。

#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;
}