Segment Tree
AlgorithmsMediumQuery range sums and apply point updates over contiguous segment splits.
Alt+Shift+S
Configuration Panel
Segment Tree Node Segments
Double-click empty canvas to create root, select node to add child or delete.
Source Array:
[0]2
[1]4
[2]5
[3]7
[4]8
[5]1
Time Complexity
O(log N) query & update
Auxiliary Space Complexity
O(N) segment tree space
Conceptual Overview
A Segment Tree is a binary tree used for storing intervals or segments. It allows querying which of the stored segments contain a given point, or performing range query sum/min/max operations in logarithmic time.
Algorithm Mechanism
Divide intervals in half recursively. Leaf nodes represent point elements of the array. Query intervals are decomposed into O(log N) disjoint segments covered by segment tree nodes.
Source: CP-Algorithms reference guide