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.
- 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.
- 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.
- 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).
- If we update a range, we mark the node as “lazy” and store the update value.
- 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:
- Range Sum Query – Mutable (Leetcode 307): The perfect introductory problem.
- Queue Reconstruction by Height (Leetcode 406): Uses a segment tree to make adding things faster.
- Falling Squares (Leetcode 699): range updates and maximum queries.
- 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 :
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.