データ構造Wiki

Segment Tree

最終更新：2019年07月22日 14:15

匿名ユーザー

- view

だれでも歓迎！編集

Segment Tree

Operations

要素数を $N$ とします.

update(i, x): $O(logN)$

$a_i=x$

fold(l, r): $O(logN)$

$a_l*...*a_r$

空間計算量: $O(N)$

Examples

なんかくれ

Summary

二分木の葉に $a_i$ を載せて節点に右の子と左の子を演算した結果を載せる.
すると, うまく区間をfoldできる.

Requirements

要素はモノイド

Blogs

セグメント木をソラで書きたいあなたに

Notes of Impl

非再帰

非再帰で書くと定数倍が早い

半開区間 or 閉区間

どっちがいいんですかね, 再帰は半開区間, 非再帰は閉区間?

Implementations

Problems

AOJ:Range Minimum Query

「Segment Tree」をウィキ内検索

最近更新されたスレッド

+新規スレッドを作成する

最近更新されたページ

急上昇Wikiランキング

急上昇中のWikiランキングです。今注目を集めている話題をチェックしてみよう！

新規Wikiランキング

最近作成されたWikiのアクセスランキングです。見るだけでなく加筆してみよう！

人気Wikiランキング

atwikiでよく見られているWikiのランキングです。新しい情報を発見してみよう！

全体ページランキング

最近アクセスの多かったページランキングです。話題のページを見に行こう！

Segment Tree

Segment Tree

Operations

Examples

Summary

Requirements

Blogs

Notes of Impl

非再帰

半開区間 or 閉区間

Implementations

Problems

メニュー

リンク

更新履歴