Overview
A Segment Tree divides an array into smaller intervals. Each node represents a segment of the array and stores information about that segment, such as its sum, minimum, maximum, or greatest common divisor.
How it works
The root represents the entire array.; Each internal node divides its segment into two smaller segments.; The process continues until each leaf represents one array element.; Each node stores an aggregate value calculated from its children.; A range query combines information from the relevant nodes.; An update modifies the affected leaf and recalculates values along its path to the root.
Key concepts
Binary tree; Array intervals; Tree nodes; Range queries; Point updates; Aggregate functions
Time complexity
operation: Build; complexity: O(n); operation: Range Query; complexity: O(log n); operation: Point Update; complexity: O(log n)
Space complexity
O(n), commonly implemented with an array of approximately 4n elements.
Example
array: 2; 4; query: Find the sum of elements from index 1 to index 4.; calculation: 4 + 1 + 7 + 3 = 15; result: 15
Applications
Competitive programming; Range sum queries; Range minimum and maximum queries; Interval-based problems; Dynamic array processing