Subscribed unsubscribe Subscribe Subscribe

Takefumi Yamamura's blog

This blog is for my memorandum.

Takefumi Yamamura's b!og

This blog is for my memorandum

segment Treeを使用してRMQをとく。

グラフ理論

RMQとは

数列a_0,a_1,...a_nがあるとき次の二つの処理をO(log n)で行う。

  • s, tが与えられたとき、a_s, a_s+1, .... , a_tの最小値を求める

  • i, xが与えられたとき、a_iの値をxに変更する

SegmentTreeとは

www.slideshare.net

www.slideshare.net

このあたりの説明が秀逸

code