セグメント木

Abstract

Explanation

Implementation

抽象化してある.

1-indexedで実装.

code:python

class SegmentTree:

def __init__(self, lst, op, e):

self.n = len(lst)

self.N = 1 << ((self.n - 1).bit_length())

self.op = op # operation

self.e = e # identity element

self.v = self._build(lst) # self.v is set to be 1-indexed for simplicity

def _build(self, lst):

# construction of a tree

return tree

def __getitem__(self, i):

# update a_i to be x

def update(self, i, x):

v, op = self.v, self.op

i += self.N

while i > 0:

i >>= 1 # move to parent

# returns answer for the query interval [l, r)

def fold(self, l, r):

N, e, v, op = self.N, self.e, self.v, self.op

left = l + N; right = r + N

L = R = e

while left < right:

left += 1

right -= 1

left >>= 1; right >>= 1

return op(L, R)

Verification

References