Segment Tree

Data structure for arrays of monoids $(M, \cdot, e)$ that supports:

• point update: $A[i] \gets v$
• range query: find $A[l] \cdot A[l+1] \cdot \ldots \cdot A[r-1]$
• lower bound: given $l$ and $x$, find the largest $r$ such that $A[l] \cdot A[l+1] \cdot \ldots \cdot A[r-1] < x$.

__init__

Arguments

• A: list[T]: array of monoid $M$
• dot: Callable[[T, T], T]: binary operator corresponding to $\cdot$
• e: T: identity element corresponding to $e$

Complexities

• time: $O(n)$
• space: $O(n)$

where $n$ represents the length of A.

__getitem__

Returns the i-th element of the array.

Arguments

• i: int: index

Returns

• T: element at index i

Complexities

• $O(1)$

__setitem__

Sets the i-th element of the array

Arguments

• i: int: index
• x: T: new element

Complexities

• $O(\log n)$

prod

Calculates the product of the subarray $A[l:r]$.

Arguments

• l: int: left endpoint of the range (inclusive)
• r: int: right endpoint of the range (exclusive)

Returns

• T: $A[l] \cdot A[l+1] \cdot \ldots \cdot A[r-1]$

Complexities

• $O(\log n)$

bisect_left

Finds the largest $r$ such that product of subarray $A[l:r]$ is less than $x$.

Arguments

• l: int: left endpoint of the range (inclusive)
• x: T: threshold

Returns

• int: largest right endpoint $r$ such that $A[l] \cdot A[l+1] \cdot \ldots \cdot A[r-1] < x$ (exclusive).

Complexities

• $O(\log n)$

Code Test

Run

Standard Output

Standard Error