segmenttree

Documentation

Overview

Segment Tree Data Structure for efficient range queries on an array of integers. It can query the sum and update the elements to a new value of any range of the array. Build: O(n*log(n)) Query: O(log(n)) Update: O(log(n)) reference: https://cp-algorithms.com/data_structures/segment_tree.html

Index

• type SegmentTree
  • func NewSegmentTree(Array []int) *SegmentTree
  • func (s *SegmentTree) Build(node int, left int, right int)
  • func (s *SegmentTree) Propagate(node int, leftNode int, rightNode int)
  • func (s *SegmentTree) Query(node int, leftNode int, rightNode int, firstIndex int, lastIndex int) int
  • func (s *SegmentTree) Update(node int, leftNode int, rightNode int, firstIndex int, lastIndex int, ...)

Types

type SegmentTree

type SegmentTree struct {
	Array       []int // The original array
	SegmentTree []int // Stores the sum of different ranges
	LazyTree    []int // Stores the values of lazy propagation
}

SegmentTree represents the data structure of a segment tree with lazy propagation

func NewSegmentTree

func NewSegmentTree(Array []int) *SegmentTree

NewSegmentTree returns a new instance of a SegmentTree. It takes an input array of integers representing Array, initializes and builds the SegmentTree.

func (*SegmentTree) Build

func (s *SegmentTree) Build(node int, left int, right int)

Build builds the SegmentTree by computing the sum of different ranges. node, leftNode and rightNode should always start with 1, 0 and len(Array)-1, respectively.

func (*SegmentTree) Propagate

func (s *SegmentTree) Propagate(node int, leftNode int, rightNode int)

Propagate propagates the lazy updates to the child nodes

func (*SegmentTree) Query

func (s *SegmentTree) Query(node int, leftNode int, rightNode int, firstIndex int, lastIndex int) int

Query returns the sum of elements of the array in the interval [firstIndex, leftIndex]. node, leftNode and rightNode should always start with 1, 0 and len(Array)-1, respectively.

func (*SegmentTree) Update

func (s *SegmentTree) Update(node int, leftNode int, rightNode int, firstIndex int, lastIndex int, value int)

Update updates the elements of the array in the range [firstIndex, lastIndex] with the new value provided and recomputes the sum of different ranges. node, leftNode and rightNode should always start with 1, 0 and len(Array)-1, respectively.