Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
Help us understand the problem. What is going on with this article?

セグ木と似たようなことが出来るアルゴリズムまとめ

セグ木と似たようなことが出来るアルゴリズムまとめ

セグ木(区分木 / Segment tree)は前処理と引き換えにある種の区間クエリが O(N) ではなく O(logN) で出来る競プロ界隈でよく見かけるアルゴリズムである. 似たようなことが出来るアルゴリズムがいくつかあるので、違いをまとめてみた.

Segment tree

O(N2) は通らないけど、O(NlogN) は通るという制約の問題は多いので、何かと頼りになる.

  • 対応している操作: 結合則が成り立つ操作、+, Min/Max, GCD, Bitwise Xor/Or 等
  • 必要なメモリ量: O(2N)~O(4N)
  • 前計算の計算量: O(N)
  • 更新の計算量: O(logN)
  • クエリの計算量: O(logN)

BIT (Binary indexed tree) / Fenwick tree

制約がきついが実装は簡単で、定数倍も軽め.

  • 対応している操作: + のみ
  • 必要なメモリ量: O(N)
  • 前計算の計算量: O(0)
  • 更新の計算量: O(logN)、加算のみで指定の値に更新とかは出来ない
  • クエリの計算量: O(logN)

Sparse table

更新ができず、操作に冪等性が必要と制約が厳しいが、クエリの計算量 O(1) は魅力.

  • 対応している操作: 結合則が成り立ち冪等性を持つ操作、Min/Max, GCD, Bitwise Or 等
  • 必要なメモリ量: O(NlogN)
  • 前計算の計算量: O(NlogN)
  • 更新の計算量: 更新は不可能
  • クエリの計算量: O(1)

Disjoint sparse table

Sparse table の上位互換? まだ調査/実装してないのでよく分からない.

  • 対応している操作: 結合則が成り立つ操作、+, Min/Max, GCD, Bitwise Xor/Or 等
  • 必要なメモリ量: O(NlogN)
  • 前計算の計算量: O(NlogN)
  • 更新の計算量: 更新は不可能
  • クエリの計算量: O(1)

Sqrt tree

今見つけたところなのでほとんど分からないけど、今まで聞いたことなかったということは有名ではない?

  • 対応している操作: 結合則が成り立つ操作、+, Min/Max, GCD, Bitwise Xor/Or 等
  • 必要なメモリ量: O(NloglogN)
  • 前計算の計算量: O(NloglogN)
  • 更新の計算量: O(√N)
  • クエリの計算量: O(1)
c-yan
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away