Illustration of working of Persistent Segment Tree in Python
Let’s walk through a detailed example step-by-step to illustrate how the persistent segment tree works:
Initial Array
- arr = [1,2,3,4,5]
Building the Initial Segment Tree
- Build the leaf nodes:
- Leaf node for
arr[0]
: value = 1- Leaf node for
arr[1]
: value = 2- Leaf node for
arr[2]
: value = 3- Leaf node for
arr[3]
: value = 4- Leaf node for
arr[4]
: value = 5- Build the internal nodes:
- Node for range [0, 1]: value = 1 + 2 = 3
- Node for range [2, 2]: value = 3
- Node for range [3, 4]: value = 4 + 5 = 9
- Node for range [0, 2]: value = 3 + 3 = 6
- Node for range [0, 4]: value = 6 + 9 = 15
Updating the Segment Tree
- Update
arr[2]
from 3 to 10:
- Create new leaf node for
arr[2]
: value = 10- Update node for range [2, 2]: new value = 10
- Update node for range [0, 2]: new value = 3 + 10 = 13
- Update node for range [0, 4]: new value = 13 + 9 = 22
Querying the Segment Tree
- Query range [1, 3] in the original tree:
- Node for range [1, 3] overlaps with range [0, 4], [0, 2], and [3, 4]
- Query range [1, 3] results in sum = 2 + 3 + 4 = 9
- Query range [1, 3] in the updated tree:
- Node for range [1, 3] overlaps with range [0, 4], [0, 2], and [3, 4]
- Query range [1, 3] results in sum = 2 + 10 + 4 = 16
This example demonstrates how the persistent segment tree maintains different versions efficiently and supports range queries on any version.
Persistent Segment Tree in Python
Persistent data structures are a powerful tool in computer science, enabling us to maintain and access multiple versions of a data structure over time. One such structure is the Persistent Segment Tree. Segment trees are versatile data structures that allow efficient querying and updating of array intervals. By making a segment tree persistent, we enhance its capability to maintain historical versions, which is particularly useful in competitive programming and real-time applications where rollback and point-in-time queries are needed. This article explores the concept, implementation in Python.
Contact Us