Segment Tree

authorImagePunit Kumar26 Mar, 2026
Segment Tree

The Segment Tree data structure is useful in this situation. As of 2026, it is still one of the most flexible and powerful tools that developers have for working with dynamic range operations. 

What is a Segment Tree?

A Segment Tree is a static tree-based way to store information about segments or intervals. You can ask which of the saved segments has a certain point or do range queries quickly with it. A Segment Tree is typically a binary tree where:
  • The leaves represent individual elements of the array.
  • The internal nodes represent the results of an operation (like sum, min, or max) performed on their children's ranges.
For an array of size n, the root of the tree represents the range [0, n-1]. Each node is recursively split into two halves until we reach the leaf nodes.

Basic of Segment Tree 

Let’s understand the operations of segment tree. 
Operation Time Complexity
Preprocessing (Building) O(n)
Range Query O(log n)
Point Update O(log n)
Space Complexity O(n) (usually allocated as 4n)

Uses of Segment Tree Data Structure?

Imagine you have an array of 1 million integers. You need to find the sum of elements from index L to R and update the value at index i thousands of times.
  1. Naive Approach:
    • Query: O(n) (Looping through the range).
    • Update: O(1).
    • Problem: If there are many queries, O(q x n) is too slow.
  2. Prefix Sum Approach:
    • Query: O(1).
    • Update: O(n) (Updating the prefix sum array).
    • Problem: If there are many updates, O(u x n) is too slow.
  3. Segment Tree Approach:
    • Query: O(log n).
    • Update: O(log n).
    • Result: Perfectly balanced for cases with high frequencies of both queries and updates.

Python Implementation of Segment Tree 

Let’s implement a segment tree python code for a range sum query. This structure is frequently used in segment tree leetcode problems. Python class SegmentTree:     def __init__(self, data):         self.n = len(data)         # Allocate 4n space to be safe for a binary tree         self.tree = [0] * (4 * self.n)         self._build(data, 1, 0, self.n - 1)     def _build(self, data, node, start, end):         if start == end:             # Leaf node stores the array element             self.tree[node] = data[start]         else:             mid = (start + end) // 2             # Recursively build left and right children             self._build(data, 2 * node, start, mid)             self._build(data, 2 * node + 1, mid + 1, end)             # Internal node stores the sum of children             self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]     def update(self, idx, val, node=1, start=0, end=None):         if end is None: end = self.n - 1         if start == end:             self.tree[node] = val             return         mid = (start + end) // 2         if idx <= mid:             self.update(idx, val, 2 * node, start, mid)         else:             self.update(idx, val, 2 * node + 1, mid + 1, end)         self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]     def query(self, L, R, node=1, start=0, end=None):         if end is None: end = self.n - 1         # Range completely outside [L, R]         if R < start or end < L:             return 0         # Range completely inside [L, R]         if L <= start and end <= R:             return self.tree[node]         # Range partially inside and partially outside         mid = (start + end) // 2         p1 = self.query(L, R, 2 * node, start, mid)         p2 = self.query(L, R, 2 * node + 1, mid + 1, end)         return p1 + p2 # Usage arr = [1, 3, 5, 7, 9, 11] st = SegmentTree(arr) print(st.query(1, 3)) # Output: 15 (3+5+7) st.update(1, 10)      # Update index 1 to 10 print(st.query(1, 3)) # Output: 22 (10+5+7)

Segment Tree and Fenwick Tree Comparison

Here is the difference between segment tree vs fenwick tree (also known as Binary Indexed Tree or BIT):
Feature Segment Tree Fenwick Tree (BIT)
Implementation Complex / Large code Simple / Concise code
Functionality Handles ANY associative operation (Min, Max, GCD) Primarily for invertible operations (Sum)
Space 4n or 2n n (More memory efficient)
Update/Query O(log n) O(log n) (Slightly faster constant factor)
Flexibility Extremely high (Lazy propagation) Limited to prefix-based operations
If you only need prefix sums and point updates, use Fenwick Tree. If you need range minimum/maximum queries or range updates (Lazy Propagation), use Segment Tree.

Use of Lazy Propagation in Segment Tree

A regular segment tree would take O(n log n) to update a range, like "Add 5 to every element from index 2 to 100." Lazy Propagation makes this better by putting off updates to child nodes until they are really needed, which brings the time down to O(log n).
  1. If we update a range, we mark the node as "lazy" and store the update value.
  2. During a future query or update, if we visit a "lazy" node, we pass the update to its children and clear the current node's lazy tag.

Problems in Segment Tree Data Structure

To master this segment tree data structure, you should solve these classic problems:
  1. Range Sum Query - Mutable (Leetcode 307): The perfect introductory problem.
  2. Queue Reconstruction by Height (Leetcode 406): Uses a segment tree to make adding things faster.
  3. Falling Squares (Leetcode 699):  range updates and maximum queries.
  4. Count of Smaller Numbers After Self (Leetcode 315): A traditional use for Segment Trees or BIT.

Properties of Segment Tree

Here are the few properties of segment tree:
Property Value/Description
Type Non-Linear / Hierarchical
Building Time O(n)
Query Time O(log n)
Update Time O(log n)
Space Complexity O(n)
Common Uses Range Sum, Min/Max, GCD, K-th element

Applications of Segment Tree

Different Query Types

  • It can answer range min, max, LCM, prime-count, and bracket-related queries.

Interval-Based Problems

  • It works well for subarray, interval, and repeated update operations.

Role in DSA

  • It is often used in coding problems that need quick range results without scanning the full array each time.
Also Read :
Our Social Channels

FAQs

Why do we use 4n space for the tree array?

For n leaves, a full binary tree has 2n-1 nodes. But because the array that represents the tree might not be properly balanced (it's a full binary tree), 4n is the safe top limit to avoid "Index Out of Bounds" issues.

Is a Segment Tree better than an Array?

Only if you have frequent updates. For a static array (no updates), a simple Prefix Sum array is much faster for queries.

Can a Segment Tree handle strings?

Yes! You can use it to keep track of hashes of substrings, which lets you check for palindromes or string equality in a dynamic environment in O(log n) time.

What is the difference between Point Update and Range Update?

A Point Update changes exactly one element. A Range Update changes every element within an interval [L, R]. Range updates usually require "Lazy Propagation" to maintain O(log n) speed.

Is Segment Tree used in real-world apps?

Yes. In GIS (Geographic Information Systems), they are used to handle spatial data searches, while in database engines, they are utilised for range-based indexing.