Segment Tree

Array Representation of Binary Tree

For a binary tree with n nodes, it can be represented by an array T .

1. The index of T is from 1 to n, T[0] is empty
2. The root of the tree is located at T[1]
3. The parent nodes are located at T[:n//2+1]
4. The leaf nodes are located at T[n//2+1:]
5. for 1 <= i <= n//2 , its children are located at T[2*i] and T[2*i+1] (may not exist)
6. for 2 <= i <= n , its parent node is located at T[i//2]

Implementation

Bottom Up

Single element update, range query, bottom up

for an array of length n, we need 2n space to store the segment tree, which contains 2n-1 values.

Algorithm	Complexity
Space	$O(n)$
Construct	$O(n)$
Update	$O(\log n)$
Query	$O(\log n)$

Top Down

Range update, range query, lazy propagation, top down

for an array of length n, we need 2n space to store the segment tree, which contains 2n-1 values. Moreover, we need some space to cache the result of calculating the range of a given index.

Algorithm	Complexity
Space	$O(n)$
Construct	$O(n)$
Update By Range	$O(\log n)$
Query	$O(\log n)$

Tests