Segment trees for range queries in Data Structures Theory - Time & Space Complexity

Time Complexity: Segment trees for range queries

O(log n)

Understanding Time Complexity

When using segment trees for range queries, it is important to understand how the time to answer queries grows as the input size increases.

We want to know how fast we can get answers when the data size gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function rangeQuery(tree, n, left, right) {
  left += n;  // shift index to leaf
  right += n;
  let result = 0;
  while (left <= right) {
    if ((left % 2) === 1) result += tree[left++];
    if ((right % 2) === 0) result += tree[right--];
    left = Math.floor(left / 2);
    right = Math.floor(right / 2);
  }
  return result;
}
    

This code performs a range sum query on a segment tree represented as an array.

Identify Repeating Operations

• Primary operation: The while loop that moves the left and right pointers up the tree.
• How many times: The loop runs roughly twice the height of the tree, which depends on the input size.

How Execution Grows With Input

As the input size grows, the height of the segment tree grows slowly, so the number of steps in the loop grows slowly too.

Input Size (n)	Approx. Operations
10	About 8 steps
100	About 14 steps
1000	About 20 steps

Pattern observation: The number of steps grows slowly, roughly with the height of the tree, which increases as the input size doubles.

Final Time Complexity

Time Complexity: O(log n)

This means the time to answer a range query grows slowly, only a little more work is needed even if the input size gets much bigger.

Common Mistake

[X] Wrong: "The range query will check every element between left and right, so it takes linear time."

[OK] Correct: The segment tree uses a clever structure to jump over parts of the range, so it does not check every element one by one.

Interview Connect

Understanding how segment trees speed up range queries shows you can work with smart data structures that handle big data efficiently.

Self-Check

"What if we changed the segment tree to support range updates as well as queries? How would the time complexity change?"