A+DS

Segment Tree

Answer range queries in O(log n) time.

A Segment Tree is a binary tree where each node stores aggregate information (like sum, min, or max) over a range of the array. It enables efficient range queries and point updates, both in O(log n) time. The root covers the entire array; each leaf stores one element.

         [36]           sum [0,5]
        /       \
     [9]        [27]       sums of halves
    /   \      /   \
  [4]  [5]  [16] [11]     smaller ranges
  / \   |   / \    |
 1   3  5  7   9  11      leaves = array

  Query [1,4]: visit [9] + [16] = 25
  Update arr[2]=10: leaf→10, parent→13, root→40

How it works

  1. 1Build: recursively split the array in half, computing sums bottom-up
  2. 2Query: traverse only nodes whose ranges overlap the query range
  3. 3Update: change a leaf and propagate new sums up to the root
  4. 4Space: stored in a flat array of size 4n (1-indexed)

Loading...