segtree

Documentation

Overview

抽象化整数セグ木、抽象化モノイドセグ木を含むパッケージです。

Index

• type IntSegTree
  • func NewIntSegTree(size int, operation func(int, int) int, unitElement int) *IntSegTree
  • func (t *IntSegTree) Find(start, end int) int
  • func (t *IntSegTree) Update(location, value int)

Examples

• IntSegTree

Types

type IntSegTree

type IntSegTree struct {
	// contains filtered or unexported fields
}

IntSegTree は、要素型をintに限定したセグメント木です。

Example

INF := 1234567890
min := func(x, y int) int {
	if x < y {
		return x
	}
	return y
}
segmentTree := NewIntSegTree(3, min, INF)
segmentTree.Update(0, 1)
segmentTree.Update(1, 2)
segmentTree.Update(2, 3)
fmt.Println(segmentTree.Find(0, 3))
fmt.Println(segmentTree.Find(1, 3))

Output:

1
2

func NewIntSegTree

func NewIntSegTree(size int, operation func(int, int) int, unitElement int) *IntSegTree

func (*IntSegTree) Find

func (t *IntSegTree) Find(start, end int) int

Find returns a_start * a_{start + 1} * ... * a_{end - 1}

i.e. returns reduced value within [start,end)

func (*IntSegTree) Update

func (t *IntSegTree) Update(location, value int)

Update は、セグメント木の要素の値を更新します。

locationで何番目の要素かを指定し(0-indexed)、valueで更新後の値を指定します。