セグメント木

セグメント木(統計木)

セグメント木のインターフェイス、実装と使用例の紹介です。
March 2, 2020, 6:01 a.m.

目次

インターフェイス

  • update(long long x, long long y)
  • find(long long x, long long y)

実装

解説:TODO

 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
void update(ll x, ll y) {
  ll i = x + N - 1;
  A.at(i) = y;
  while (i > 0) {
    i = (i-1)/2;
    A.at(i) = min(A.at(i*2+1), A.at(i*2+2));
  }
}

ll findRec(ll x, ll y, ll n, ll l, ll r) {
  // i)        l      r    x   y
  // i)  x   y l      r
  if (r <= x || y <= l) return INFTY;
  // iii)  x    l     r    y
  if (x <= l && r <= y) return A.at(n);
  // iv)   x    l    y   r
  return min(
    findRec(x, y, n*2+1, l, (l+r)/2),
    findRec(x, y, n*2+2, (l+r)/2, r)
  );
}

ll find(ll x, ll y) {
  return findRec(x, y+1, 0, 0, N);
}

使用例

TODO