Segment Tree Data Structure

Learn Segment Tree Data Structure with practical examples, explanations, best practices, and real-world coding techniques.

What Is a Segment Tree?

A Segment Tree is a tree-based data structure used to efficiently answer queries over ranges of an array while also supporting updates to individual elements. It is especially useful when an application needs to perform many range queries and updates on the same dataset.

A range query asks for information about a continuous portion of an array. For example, given an array of numbers, we might need to repeatedly calculate the sum, minimum, maximum, or another aggregate value between two indexes.

A straightforward loop can answer one range query in O(n) time in the worst case. A Segment Tree preprocesses the array into a hierarchical structure so that range queries and point updates can be performed in O(log n) time.

Why Use a Segment Tree?

Suppose an array contains thousands or millions of values and an application repeatedly asks questions such as:

  • What is the sum between indexes 10 and 100?
  • What is the minimum value between two positions?
  • What is the maximum value in a particular range?
  • What happens to the range result after one array value changes?

Recalculating every requested range from the original array can become expensive. A Segment Tree stores information about smaller ranges and combines those results when answering larger range queries.

Segment Tree Example

Consider the following array: 

[2, 4, 6, 8]

For a sum Segment Tree, the root can represent the complete range [0, 3]. Its children represent smaller ranges: 

                [0, 3] = 20
                 /      \
          [0, 1] = 6    [2, 3] = 14
           /    \         /     \
      [0] = 2 [1] = 4 [2] = 6 [3] = 8

Each internal node stores the result for the range represented by that node. For a sum Segment Tree, the parent value is the sum of its two children.

How a Segment Tree Represents Ranges

A Segment Tree recursively divides an array into smaller intervals. The root represents the entire array. Each internal node divides its interval into a left and right segment until individual elements are reached.

For an array of eight elements, the ranges can be divided approximately as: 

[0, 7]
├── [0, 3]
│   ├── [0, 1]
│   └── [2, 3]
└── [4, 7]
    ├── [4, 5]
    └── [6, 7]

This recursive division is what allows the Segment Tree to answer a range query by combining only the relevant nodes instead of examining every element in the requested range.

Building a Segment Tree

Building a Segment Tree starts with the original array. The tree recursively divides the array into two parts. When the recursion reaches a single element, that element becomes a leaf node.

The parent node is then calculated by combining the values of its left and right children.

For a sum Segment Tree: 

tree[node] =
    tree[leftChild] + tree[rightChild]

The same general structure can be adapted for other operations such as minimum or maximum, provided the operation can combine the results of child ranges appropriately.

Range Sum Query

One of the most common applications of a Segment Tree is the range sum query. Given an array and two indexes left and right, the query calculates the sum of all elements within that inclusive range.

For example, given: 

[2, 4, 6, 8, 10, 12]

Query: sum(1, 4)

Result:
4 + 6 + 8 + 10 = 28

Instead of scanning indexes 1 through 4 every time, the Segment Tree combines nodes whose ranges completely belong to the requested interval.

How a Range Query Works

During a Segment Tree range query, each node falls into one of three situations.

  1. Complete overlap: the node's range is completely inside the requested range, so its stored value can be returned directly.
  2. No overlap: the node's range is outside the requested range, so it contributes nothing.
  3. Partial overlap: the node's range intersects the query, so both child ranges are examined.

This complete-overlap, no-overlap, and partial-overlap logic is the key to efficient Segment Tree range queries.

Point Update

A Segment Tree can also update an individual array element efficiently. Suppose an array value changes from 6 to 10. The corresponding leaf node is updated first.

The change is then propagated upward through the tree so that every affected parent range receives its new value. 

Before:

[2, 4, 6, 8]

Update index 2:
6 → 10

After:

[2, 4, 10, 8]

Only the nodes along the path from the changed element to the root need to be recalculated. This is why a point update takes O(log n) time.

Segment Tree Array Representation

A Segment Tree is often stored inside a normal array rather than creating separate objects for every tree node. This is similar to the array representation used by heaps.

If a node is stored at index i, common zero-based indexing formulas are: 

Left child  = 2 * i + 1
Right child = 2 * i + 2

The exact memory layout depends on the implementation, but allocating around 4n positions is a common simple approach for a recursive Segment Tree implementation.

Segment Tree Construction in JavaScript

The following implementation creates a Segment Tree for range sum queries. It uses recursive construction and stores the tree in an array.

Segment Tree Range Query Logic

A range query recursively visits only the nodes necessary to answer the requested interval. When a node is completely covered by the query range, its stored value is used immediately.

This avoids repeatedly calculating the same partial sums and is the main performance advantage over a direct array traversal.

Segment Tree Update Logic

To update one array position, the algorithm follows the path from the root toward the corresponding leaf. After updating the leaf, each affected ancestor is recalculated.

For a sum tree, every affected parent is recalculated using: 

tree[node] =
    tree[leftChild] + tree[rightChild]

Segment Tree Time Complexity

One of the main advantages of a Segment Tree is that both range queries and point updates can be performed efficiently.

Operation Time Complexity
Build O(n)
Range Query O(log n)
Point Update O(log n)
Space O(n)

The O(log n) query and update complexity makes Segment Trees useful when a program needs a large number of range operations and the underlying data changes over time.

Types of Segment Tree Queries

Although range sum is one of the easiest examples to understand, the Segment Tree concept is not limited to addition.

  • Range sum: calculate the sum of values in an interval.
  • Range minimum: find the smallest value in an interval.
  • Range maximum: find the largest value in an interval.
  • Range greatest common divisor: calculate the GCD over a range.
  • Custom associative operations: combine information from child segments according to the problem.

The operation used by the tree determines what each internal node stores and how two child results are combined.

Segment Tree vs Prefix Sum

Prefix sums are excellent when the array does not change frequently. A prefix sum array can answer a range sum query in O(1) time after O(n) preprocessing.

However, changing one original array value requires updating many prefix values. A Segment Tree provides a useful alternative when both range queries and point updates are required.

Structure Range Query Point Update
Prefix Sum O(1) O(n)
Segment Tree O(log n) O(log n)

Segment Tree vs Fenwick Tree

A Fenwick Tree, also called a Binary Indexed Tree, can efficiently support prefix-based calculations and point updates. Both structures can be used for certain range sum problems, but they provide different capabilities.

Segment Trees are generally more flexible because their nodes can represent different range aggregates and can be extended to support more advanced query and update techniques.

Fenwick Trees usually have a simpler implementation and lower memory overhead for problems that only require operations naturally supported by prefix aggregation.

Advantages of Segment Trees

  • Efficient O(log n) range queries.
  • Efficient O(log n) point updates.
  • Supports different types of range aggregates.
  • Works well when data changes between queries.
  • Can be extended for more advanced range-update problems.

Limitations of Segment Trees

  • More complex to implement than a simple array or prefix sum.
  • Requires additional memory.
  • Recursive implementations can be harder for beginners to debug.
  • May be unnecessary when only a small number of range queries are required.
  • Some advanced operations require techniques such as lazy propagation.

When Should You Use a Segment Tree?

Consider a Segment Tree when a problem has a large array or sequence and repeatedly performs range queries and updates.

It is particularly useful in algorithmic problems involving dynamic arrays, competitive programming, interval calculations, and systems that need to maintain aggregate information while values change.

Common Segment Tree Problems

  • Range sum queries with point updates
  • Range minimum and maximum queries
  • Dynamic interval calculations
  • Maintaining aggregate values while data changes
  • Counting or combining information across ranges
  • Advanced range updates using lazy propagation

What Is Lazy Propagation?

Basic Segment Trees are especially useful for point updates. Some problems, however, require updating an entire range, such as adding a value to every element between two indexes.

Lazy propagation is an advanced Segment Tree technique that postpones some updates until the affected nodes actually need to be processed. This can make range updates and range queries efficient.

Lazy propagation is an extension of the basic Segment Tree concept and is commonly studied after understanding construction, range queries, and point updates.

Practical Mental Model

A useful way to think about a Segment Tree is as a collection of precomputed answers for progressively larger ranges. 

Array
  ↓
Split into smaller ranges
  ↓
Store an answer for each range
  ↓
Combine relevant ranges during a query
  ↓
Update only affected ranges when a value changes

Once this idea is clear, the recursive implementation becomes much easier to understand.

Key Takeaways

  • A Segment Tree is a tree-based data structure for range queries and updates.
  • It recursively divides an array into smaller intervals.
  • Each node stores information about a particular range.
  • Range queries can typically be answered in O(log n) time.
  • Point updates can typically be performed in O(log n) time.
  • A basic Segment Tree can be built in O(n) time.
  • Segment Trees can support sums, minimums, maximums, and other range aggregates.
  • Lazy propagation extends Segment Trees to efficiently handle range updates.
  • Segment Trees are especially useful when data changes and range queries are frequent.

Code Examples 

class SegmentTree {
  constructor(arr) {
    this.n = arr.length;
    this.tree = new Array(this.n * 4).fill(0);

    this.build(arr, 1, 0, this.n - 1);
  }

  build(arr, node, left, right) {
    if (left === right) {
      this.tree[node] = arr[left];
      return;
    }

    const mid = Math.floor((left + right) / 2);

    this.build(arr, node * 2, left, mid);
    this.build(arr, node * 2 + 1, mid + 1, right);

    this.tree[node] =
      this.tree[node * 2] + this.tree[node * 2 + 1];
  }

  query(queryLeft, queryRight, node = 1, left = 0, right = this.n - 1) {
    if (queryRight < left || right < queryLeft) {
      return 0;
    }

    if (queryLeft <= left && right <= queryRight) {
      return this.tree[node];
    }

    const mid = Math.floor((left + right) / 2);

    const leftSum = this.query(
      queryLeft,
      queryRight,
      node * 2,
      left,
      mid
    );

    const rightSum = this.query(
      queryLeft,
      queryRight,
      node * 2 + 1,
      mid + 1,
      right
    );

    return leftSum + rightSum;
  }

  update(index, value, node = 1, left = 0, right = this.n - 1) {
    if (left === right) {
      this.tree[node] = value;
      return;
    }

    const mid = Math.floor((left + right) / 2);

    if (index <= mid) {
      this.update(index, value, node * 2, left, mid);
    } else {
      this.update(index, value, node * 2 + 1, mid + 1, right);
    }

    this.tree[node] =
      this.tree[node * 2] + this.tree[node * 2 + 1];
  }
}

const numbers = [2, 4, 6, 8, 10, 12];

const segmentTree = new SegmentTree(numbers);

console.log(segmentTree.query(1, 4)); // 28

segmentTree.update(2, 10);

console.log(segmentTree.query(1, 4)); // 32
    
class MinSegmentTree {
  constructor(arr) {
    this.n = arr.length;
    this.tree = new Array(this.n * 4).fill(Infinity);

    this.build(arr, 1, 0, this.n - 1);
  }

  build(arr, node, left, right) {
    if (left === right) {
      this.tree[node] = arr[left];
      return;
    }

    const mid = Math.floor((left + right) / 2);

    this.build(arr, node * 2, left, mid);
    this.build(arr, node * 2 + 1, mid + 1, right);

    this.tree[node] = Math.min(
      this.tree[node * 2],
      this.tree[node * 2 + 1]
    );
  }

  query(queryLeft, queryRight, node = 1, left = 0, right = this.n - 1) {
    if (queryRight < left || right < queryLeft) {
      return Infinity;
    }

    if (queryLeft <= left && right <= queryRight) {
      return this.tree[node];
    }

    const mid = Math.floor((left + right) / 2);

    return Math.min(
      this.query(queryLeft, queryRight, node * 2, left, mid),
      this.query(queryLeft, queryRight, node * 2 + 1, mid + 1, right)
    );
  }
}

const values = [8, 3, 7, 2, 9, 4];

const tree = new MinSegmentTree(values);

console.log(tree.query(1, 4)); // 2
console.log(tree.query(0, 2)); // 3

Pro Tip

When you see a problem that repeatedly asks for information over array ranges while values are also changing, think about a Segment Tree. If the problem only needs static range sums, a prefix sum may be simpler; if it needs dynamic range queries and updates, a Segment Tree is often a useful approach.

🎨 IgKnight Docs

Master HTML, CSS, JS, Python, .NET and more with easy-to-follow lessons and practical code examples.

© 2025 IgKnight Learning Platform. All rights reserved.