CKP

Pure Python implementations of competitive programming algorithms.

View the Project on GitHub 123jimin/ckp

Segment Tree

Note: this submodule is work-in-progress.

CKP provides some generic implementations of segment trees, together with specialized implementations for several common cases.

For ease of use, ckp.data_structure.segment_tree uses object-oriented APIs.

General Structure

Many, but not all, segment trees’ APIs look like a subset of this:

class SegmentTree:
    def __init__(self, init_values: list ...): pass
    def __len__(self) -> int: pass
    def __str__(self) -> str: pass
    def __iter__(self): pass

    def __getitem__(self, ind: int): pass
    def sum_range(self, start: int, end: int): pass
    def sum_all(self): pass

    def __setitem__(self, ind: int, value): pass
    def set_range(self, start: int, end: int, value): pass

    def add_to(self, ind: int, value): pass
    def add_to_range(self, start: int, end: int, value): pass

    def mul_to(self, ind: int, value): pass
    def mul_to_range(self, start: int, end: int, value): pass
    
    def mul_add_to(self, ind: int, m, d): pass
    def mul_add_to_range(self, start: int, end: int, m, d): pass

The API does not make use of slice objects, because of it would likely induce an overhead.

Base

A segment tree can be based on a monoid or a ring, potentially non-commutative.

Operation Types

An operation may be applied either on a range or an element.

For a segment tree on a monoid, there can be two kinds of operations:

For a segment tree on a ring, these operations are possible:

Query Types

There can be other types of operations, such as getting range max elements for a segment tree with the group of natural numbers with addition as the base monoid.

Implementations

Monoid

Here is the table of specific segment trees implemented by CKP.

Name a[i] = v a[i] += d Get a[i] Sum a[i:j]
list ⚠️ ⚠️
MonoidSumSegmentTree ⚠️ ⚠️
MonoidAddSegmentTree ⚠️
MonoidSegmentTree

There are some specialized instances for commonly occurring monoids:

Merge Sort

Persistent