Skip to main content

Segment Tree

This page provides links to solutions for problems that use the Fenwick Tree data structure.

Overview​

A Segment tree is a type of data structure that allows range operations, such as finding total, minimum, maximum, distinct value within a range, in O(log N)\text{O(log N)} time complexity.

Additionally, it can perform point and range updates in O(log N)\text{O(log N)} time as well. Despite its name, a segment tree is actually stored as an array of elements.

Build Segment Tree​

Let's build a range sum segment tree for following array.

arr=[14,71,37,93,−1]\text{arr} = [14, 71, 37, 93, -1]

Even thought it is called a segment tree, it is stored as an array. To build a segment tree for an input array with 55 elements, we start by creating an array of size 44 times the size of an input array.

Since there are 55 elements in an input array, build function will start with range 0−40-4. Segment tree array index will be at 00.

segment-tree-1.svg

Build function splits the range in half, the left segment range becomes 0−20-2. Segment tree array index when it goes to left subtree becomes 2∗parentIndex+1=2∗0+1=12 * \text{parentIndex} + 1 = 2 * 0 + 1 = 1.

segment-tree-2.svg

Recursively splitting the left subtree further, we get the left segment range as 0−10-1. Segment tree array index becomes 33.

segment-tree-3.svg

Further splitting the left subtree, the segment reduces to a single point 0−00-0. At this point, we assign the element from the input array at 0th0^{\text{th}} index to current segment tree array index, so we assign tree[77] = arr[00].

segment-tree-4.svg

After reaching the 0−00-0 segment, we cannot split the left subtree further. The build function backtracks and splits the right subtree of the parent into two halves, resulting in a single point segment 1−11-1.

Since this is a single point, we assign the value from the input array at 1st1^{\text{st}} index to the current segment tree array index. Therefore, we assign tree[88] = arr[11].

segment-tree-5.svg

At this point, we have completed splitting both the left and right subtree of the segment range 0−10-1. We then apply the sum function to combine the values from both child indexes and assign the result to the current segment tree array index. Thus we assign tree[33] = tree[77] + tree[88] = 8585.

segment-tree-6.svg

After completing the recursive process described above, the segment tree will be fully built. Below are snapshots of each step.

segment-tree-7.svg
segment-tree-8.svg
segment-tree-9.svg
segment-tree-10.svg
segment-tree-11.svg
segment-tree-12.svg
segment-tree-13.svg
long[] arr;
long[] tree;

public SegmentTreeSum(long[] arr) {
  this.arr = arr;
  this.tree = new long[4 * arr.length];
  build(0, 0, arr.length - 1);
}

public void build(int treeIndex, int fromArrIndex, int toArrIndex) {
  if (fromArrIndex == toArrIndex) {
    tree[treeIndex] = arr[fromArrIndex];
  } 
  else {
    int mid = fromArrIndex + (toArrIndex - fromArrIndex) / 2;
    build(2 * treeIndex + 1, fromArrIndex, mid);
    build(2 * treeIndex + 2, mid + 1, toArrIndex);
    tree[treeIndex] = tree[2 * treeIndex + 1] + tree[2 * treeIndex + 2];
  }
}

Use Segment Tree​

Let's use the segment tree to find the range sum of indexes 2−32-3 in an input array.

We begin calculation of the range sum from the root node, which represent 0th0^{\text{th}} index of a segment tree array and range 0−40-4 of an input array.

There are 33 main conditions to consider at any given node:

  • Outside of Input Range: Return 00 if the range at the current node falls entirely outside the input range.

  • Subset of Input Range: Return the precomputed sum from the segment tree if the range at the current node is part of input range.

  • Partially Overlaps Input Range: If range at current node partially overlaps with input range recursively calculate values from left and right subtree and return the result.

The range at current node, 0−40-4, partially overlaps input range 2−32-3, therefore we recursively calculate value from left and right subtree.

segment-tree-14.svg

Let's recursively calculate the value from the left subtree. The range at the current node, 0−20-2, partially overlaps with the input range 2−32-3, therefore we recursively calculate the values from its left and right subtrees.

segment-tree-15.svg

The next node in the path has a range of 0−10-1, which lies entirely outside the input range 2−32-3, therefore we return 00 from the left subtree and stop the recursion for the left subtree.

segment-tree-16.svg

Let's continue the recursive process on the right subtree.

The next node in the right subtree has a range of 2−22-2, which is part of input range 2−32-3. As a result, we return the precomputed value 3737 from the right subtree and stop the recursion for the right subtree.

segment-tree-17.svg

At this stage, the values from both subtrees at the node with the range 0−20-2 are ready. We add these values together and backtrack to the parent node.

segment-tree-18.svg

Let's continue the above process, until we calculate the sum for the range 2−32-3.

The node's range partially overlaps the input range.

segment-tree-19.svg

The node's range is subset of the input range.

segment-tree-20.svg

The node's range is outside the input range.

segment-tree-21.svg

Backtracking to get sum for input range.

segment-tree-22.svg

Therefore, the range sum from index 2−32-3 is 37+93=13037 + 93 = 130.

public int rangeSum(int treeIndex, int from, int to) {
  return rangeSumInternal(treeIndex, from, to, 0, arr.length - 1);
}

public int rangeSumInternal(int treeIndex, int fromArrIndexInput, int toArrIndexInput, 
  int fromArrIndex, int toArrIndex) {
  // range at current node is part of input range.
  // fromArrIndexInput <= fromArrIndex <= toArrIndex <= toArrIndexInput
  if (fromArrIndexInput <= fromArrIndex && toArrIndex <= toArrIndexInput) {
    return tree[treeIndex];
  }
  // range at current node is out side the input range.
  // case 1: fromArrIndex < toArrIndex < fromArrIndexInput < toArrIndexInput 
  // case 2: fromArrIndexInput < toArrIndexInput < fromArrIndex < toArrIndex
  else if (toArrIndex < fromArrIndexInput || toArrIndexInput < fromArrIndex) {
    return 0;
  }
  // partial overlap
  else {
    int mid = fromArrIndex + (toArrayIndex - fromArrIndex) / 2;
    // calculate sum from left subtree.
    int left = rangeSumInternal(
      2 * treeIndex + 1, 
      fromArrIndexInput, toArrIndexInput, 
      fromArrIndex, mid
    );
    // calculate sum from right subtree.
    int right = rangeSumInternal(
      2 * treeIndex + 2, 
      fromArrIndexInput, toArrIndexInput, 
      mid + 1, toArrIndex
    );
    // sum left and right subtree values together and return.
    return left + right;
  }
}

Update Segment Tree​

There are two ways to update segment tree as below:

Point Update​

Let's update the element at 4th4^{\text{th}} index of an input array from −1-1 to 11.

old_arr=[14,71,37,93,−1]\text{old\_arr} = [14, 71, 37, 93, -1] new_arr=[14,71,37,93,1]\text{new\_arr} = [14, 71, 37, 93, 1]
info

Note that the update here replaces the old value with the new value, rather than adding the new value to the existing one.

We begin the segment tree update from the root node, which represents the 0th0^{\text{th}} index of the segment tree array and the range 0−40-4 of the input array.

There are 33 main conditions to consider at any given node:

  • Outside of Update Point: No updates are required if the range at the current node falls entirely outside the update point.

  • Equals the Update Point: If range at current node range equals the update point, update the value at the current node.

  • Partially Overlaps Update Point: If the range at the current node partially overlaps with the update point, recursively update the subtree in which the point is present.

The range at the current node, 0−40-4, partially overlaps with the update point 44. During the segment tree construction, ranges are split into halves. The left subtree covers the range 0−20-2, and the right subtree covers the range 3−43-4. Since the update point 44 falls within the range of the right subtree, we proceed to recursively update the right subtree.

segment-tree-23.svg

The range of the current node is 3−43-4, and the update point still lies within the right subtree.

segment-tree-24.svg

The range at the current node is 4−44-4, which matches the update point. We update the value at this node to 11 and then backtrack to update the parent nodes until we return to the root.

segment-tree-25.svg

While backtracking, we retrieve the old value of 9393 from the left subtree and the newly assigned value of 11 from the right subtree. We then update the node with the range 3−43-4 to the new value of 93+1=9493 + 1 = 94.

segment-tree-26.svg

Upon further backtracking, we reach the root node, where we retrieve the old value of 122122 from the left subtree and the new value of 9494 from the right subtree. We then update the root node to the new value of 122+94=216122 + 94 = 216.

segment-tree-27.svg

Once the root node update process is complete, we obtain the new segment tree as shown below.

segment-tree-28.svg
public void pointUpdate(int arrIndex, int value) {
  return pointUpdateInternal(0, arrIndex, value, 0, arr.length - 1);
}

public void pointUpdateInternal(int treeIndex, int arrIndexInput, int value, 
  int fromArrIndex, int toArrIndex) {
  // out of the input range.
  // case 1: arrIndexInput < fromArrIndex < toArrIndex
  // case 2: fromArrIndex < toArrIndex < arrIndexInput
  if (arrIndexInput < fromArrIndex || toArrIndex < arrIndexInput) {
    return;
  }
  // if an index is found.
  else if (fromArrIndex == toArrIndex) {
    tree[treeIndex] = value;
  }
  // partial overlap
  else {
    int mid = fromArrIndex + (toArrIndex - fromArrIndex) / 2;
    // check if update point is on the left subtree.
    if (arrIndexInput < mid) {
      pointUpdateInternal(2 * treeIndex + 1, 
        arrIndexInput, value
        fromArrIndex, mid
      );
    }
    // else update point is on the right subtree.
    else {
      pointUpdateInternal(2 * treeIndex + 2, 
        arrIndexInput, value,
        mid + 1, toArrIndex
      );
    }
    tree[treeIndex] = tree[2 * treeIndex + 1] + tree[2 * treeIndex + 2];
  }
}

Range Update​

Let's update the elements in original within the range 3−43-4 to −1-1.

old_arr=[14,71,37,93,1]\text{old\_arr} = [14, 71, 37, 93, 1] new_arr=[14,71,37,−1,−1]\text{new\_arr} = [14, 71, 37, -1, -1]
info

Note that with range updates, the update function cannot directly modify the actual array, as doing so may require O(N)\text{O(N)} time, where N\text{N} is total number of elements in an array. Instead, the update function will only modify the segment tree array only.

We begin the segment tree update from the root node, which represents the 0th0^{\text{th}} index of the segment tree array and the range 0−40-4 of the input array.

There are 44 main conditions to consider at any given node:

  • Outside of Input Range: No updates are required if the range at the current node falls entirely outside the input range.

  • Subset of Input Range:

    • Single Point: If the range at the current node reduces to a single point, update the value at current node in segment tree.
    • Range Overlap: If the range at the current node is subset of update range, recursively update both subtrees.

  • Partially Overlaps Input Range: If the range at the current node partially overlaps with the input range recursively update both subtrees.

info

The only difference between a range update and a point update lies in point 33: in a range update, both subtrees are recursively updated, whereas in a point update, only the subtree containing the update point is updated.

The range of the current node, 0−40-4, partially overlaps with the update range, 3−43-4, so we update both subtrees, recursively.

segment-tree-29.svg

Let's update the left subtree first. The range at the current node, 0−20-2, falls completely outside the update range, 3−43-4, so we return and proceed with the right subtree of parent node.

segment-tree-30.svg

The range of the current node, 3−43-4, completely overlaps with the update range, 3−43-4, so we recursively update both subtrees.

segment-tree-31.svg

Let's update the left subtree first. The range at the current node, 3−33-3, has been reduced to a single point, so we update the value of the current node to the update value, −1-1.

segment-tree-32.svg

Let's also update the right subtree. The range at the current node, 4−44-4, has been reduced to a single point, so we update the value of the current node to the update value, −1-1.

segment-tree-33.svg

At this point, the function will backtrack, and once it reaches the root node, the update will be complete. During backtracking, it will first reach the node with the range 3−43-4 and update its value using the new values from the left and right subtrees.

segment-tree-34.svg

On further backtracking, the update function will reach the root node, which will pull the old value of 122122 from the left subtree and the new value of −2-2 from the right subtree and assign a value of 122+(−2)=120122 + (-2) = 120 to current node.

segment-tree-35.svg

Once the root node update process is complete, we obtain the new segment tree as shown below.

segment-tree-36.svg
public void rangeUpdate(int from, int to, int value) {
  return rangeUpdateInternal(0, from, to, value, 0, arr.length - 1);
}

public void rangeUpdateInternal(int treeIndex, int fromArrIndexInput,
  int toArrIndexInput, int value, int fromArrIndex, int toArrIndex) {
  // outside of the input range
  // case 1: fromArrIndexInput < toArrIndexInput < fromArrIndex < toArrIndex
  // case 2: fromArrIndex < toArrIndex < fromArrIndexInput < toArrIndexInput
  if (toArrIndexInput < fromArrIndex || toArrIndex < fromArrIndexInput) {
    return;
  }
  // input range reduces to single point
  else if (fromArrIndex == toArrIndex) {
    tree[treeIndex] = value;
  }
  // partial overlap or complete overlap
  else {
    int mid = fromArrIndex + (toArrIndex - fromArrIndex) / 2;
    rangeUpdateInternal(2 * treeIndex + 1, 
      fromArrIndexInput, toArrIndexInput, value, 
      fromArrIndex, mid
    );
    rangeUpdateInternal(2 * treeIndex + 2, 
      fromArrIndexInput, toArrIndexInput, value, 
      mid + 1, toArrIndex
    );
    tree[treeIndex] = tree[2 * treeIndex + 1] + tree[2 * treeIndex + 2];
  }
}

Lazy Propagation​

A range update in a segment tree can take O(N)\text{O(N)} time, where N\text{N} is the number of elements in the array. To reduce the update time to O(log N)\text{O(log N)}, you can use a technique called lazy propagation.

Lazy Range Update​

Let's update the elements in original within the range 3−43-4 to 1010.

old_arr=[14,71,37,−1,−1]\text{old\_arr} = [14, 71, 37, -1, -1] new_arr=[14,71,37,10,10]\text{new\_arr} = [14, 71, 37, 10, 10]

We begin the segment tree update from the root node, which represents the 0th0^{\text{th}} index of the segment tree array and the range 0−40-4 of the input array.

There are 33 main conditions to consider at any given node:

  • Outside Input Range: No updates are required if the range at the current node falls entirely outside the input range.

  • Subset of Input Range: If the range at the current node is part of the input range, update the value of the current node to the input update value multiplied by the number of nodes in both subtrees of the current node. Also, lazily update the left and right subtrees using the lazy array.

  • Partially Overlaps Input Range: If the range at the current node partially overlaps with the input range, recursively update both subtrees.

The range of the current node, 0−40-4, partially overlaps with the update range, 3−43-4, so we update both subtrees, recursively.

segment-tree-37.svg
info

Notice how we are using another array, called lazy, to delay updates to the left and right subtrees when the current node's range matches the input range.

Let's recursively update left subtree first. The range of the current node, 0−20-2, falls completely outside the update range, 3−43-4, so we return from the update function without taking any action.

segment-tree-38.svg


Let's update the right subtree now. The range of the current node, 3−43-4, is a subset of the update range, 3−43-4. Therefore, we update the value of the current node to 2020. This value is calculated as the update value(1010) multiplied by the number of nodes in the left and right subtrees of the current node: 10×((4−3)+1)=2010 \times ((4 - 3) + 1) = 20.

info

To calculate the number of nodes in the current node's left and right subtrees, we simply subtract the lower limit, 33, from the upper limit, 44, of the current node and add one.

Additionally, we lazily update the left and right subtrees of the current node with the value 1010, by modifying the lazy array.

segment-tree-39.svg


At this point, the lazy range update function begins to backtrack. The first node it reaches is the root node. The root node retrieves the old value of 122122 from the left subtree and the new value of 2020 from the right subtree, then assigns itself the sum 122+20=142122 + 20 = 142.

segment-tree-40.svg


Once the root node is updated, we get segment tree as below.

segment-tree-41.svg


public void rangeUpdateLazy(int from, int to, int value) {
  return rangeUpdateLazyInternal(0, from, to, value, 0, arr.length - 1);
}

public void rangeUpdateLazyInternal(int treeIndex, int fromArrIndexInput,
  int toArrIndexInput, int value, int fromArrIndex, int toArrIndex) {
  // propagate old lazy value from the current node to left and righ subtree
  if (lazy[treeIndex] != 0) {
    int totalLazyValue = lazy[treeIndex] * (toArrIndex - fromArrIndex + 1);
    tree[treeIndex] = totalLazyValue;
    if(fromArrIndex != toArrIndex) {
      lazy[2 * treeIndex + 1] = lazy[treeIndex];
      lazy[2 * treeIndex + 2] = lazy[treeIndex];
    }
    lazy[treeIndex] = 0
  }
  // outside of the input range
  // case 1: fromArrIndexInput < toArrIndexInput < fromArrIndex < toArrIndex
  // case 2: fromArrIndex < toArrIndex < fromArrIndexInput < toArrIndexInput
  if (toArrIndexInput < fromArrIndex || toArrIndex < fromArrIndexInput) {
    return;
  }

  // subset of input range
  // fromArrIndexInput <= fromArrIndex <= toArrIndex <= toArrInputIndex
  else if (fromArrIndexInput <= fromArrIndex && toArrIndex <= toArrInputIndex) {
    int totalUpdateValue = value * (toArrIndex - fromArrIndex + 1);
    tree[treeIndex] = totalUpdateValue;
    if(fromArrIndex != toArrIndex) {
      // delay propagation of current updates to child nodes
      lazy[2 * treeIndex + 1] = value;
      lazy[2 * treeIndex + 2] = value;
    }
    lazy[treeIndex] = 0;
  }
  // partial overlap
  else {
    int mid = fromArrIndex + (toArrIndex - fromArrIndex) / 2;
    rangeUpdateLazyInternal(2 * treeIndex + 1, 
      fromArrIndexInput, toArrIndexInput, value, 
      fromArrIndex, mid
    );
    rangeUpdateLazyInternal(2 * treeIndex + 2, 
      fromArrIndexInput, toArrIndexInput, value, 
      mid + 1, toArrIndex
    );
    tree[treeIndex] = tree[2 * treeIndex + 1] + tree[2 * treeIndex + 2]
  }
}

Lazy Range Query​

Let's use the segment tree to find the range sum of indexes 2−32−3 in an input array using lazy range query.

There are 33 main conditions to consider at any given node:

  • Outside of Input Range: Return 00 if the range at the current node falls entirely outside the input range.

  • Subset of Input Range: If the range at the current node is part of input range and if lazy value is zero, return the precomputed sum from the segment tree.

  • Partially Overlaps Input Range: If range at current node partially overlaps with input range recursively calculate values from left and right subtree and return the result.

info

In a lazy range query, we also propagate and retrieve values from the lazy array.

The range at current node, 0−40-4, partially overlaps input range 2−32-3, therefore we recursively calculate value from left and right subtree.

segment-tree-42.svg


Let's first recursively calculate the sum from the left subtree. The range at current node, 0−20-2, partially overlaps input range 2−32-3, therefore we recursively calculate value from left and right subtree.

segment-tree-43.svg


Continuing further into the left subtree, the range of the current node, 0−10-1, is completely outside the input range, 2−32-3. Therefore, we return 00.

segment-tree-44.svg


Let's recursively calculate the sum from the right subtree of parent node. The range at the current node, 2−22-2 is subset of input range 2−32-3, so we return precomputed value 3737 from the current node.

segment-tree-45.svg


At this point, the update function backtracks and retrieves 00 from the left subtree and 3737 from the right subtree.

segment-tree-46.svg


Let's recursively calculate the sum from the right subtree of the root node. The range of the current node, 3−43-4, partially overlaps with the input range, 2−32-3. Therefore, we calculate the sum from both the left and right subtrees.

segment-tree-47.svg


Let's calculate the sum from the left subtree first. The range of the current node, 3−33-3, is a subset of the input range, 2−32-3. Therefore, we return the precomputed value. However, since the node 3−33-3 has a lazy value, it should be propagated first, and the new value for the node should be recalculated.

segment-tree-48.svg


Let's calculate the sum from right subtree. The range of the current node, 4−44-4, falls outside the input range 2−32-3. Thereforce, we return 00 from the right subtree.

segment-tree-49.svg


At this point lazy range update function backtracks and calculates sum value over range 2−32-3 as 37+10=4737 + 10 = 47.

segment-tree-50.svg


public int rangeSumLazy(int from, int to) {
  return rangeSumLazyInternal(0, from, to, 0, arr.length - 1);
}

public int rangeSumLazyInternal(int treeIndex, int fromArrIndexInput,
  int toArrIndexInput, int fromArrIndex, int toArrIndex) {
  // propagate old lazy value
  if (lazy[treeIndex] != 0) {
    int totalLazyValue = lazy[treeIndex] * (toArrIndex - fromArrIndex + 1)
    tree[treeIndex] = tree[treeIndex] + totalLazyValue
    if(fromArrIndex != toArrIndex) {
      lazy[2 * treeIndex + 1] = lazy[treeIndex]
      lazy[2 * treeIndex + 2] = lazy[treeIndex]
    }
    lazy[treeIndex] = 0
  }	
  // outside of input range
  // fromArrIndexInput < toArrIndexInput < fromArrIndex < toArrIndex
  // fromArrIndex < toArrIndex < fromArrIndexInput < toArrIndexInput
  if (toArrIndexInput < fromArrIndex || toArrIndex < fromArrIndexInput) {
    return 0;
  }

  // subset of input range
  // fromArrIndex <= fromArrIndexInput <= toArrInputIndex <= toArrIndex
  else if (fromArrIndexInput <= fromArrIndex && toArrIndex <= && toArrInputIndex) {
    return tree[treeIndex]
  }
  // partial overlap
  else {
    int mid = fromArrIndex + (toArrIndex - fromArrIndex) / 2;
    int left = rangeSumLazyInternal(2 * treeIndex + 1, 
      fromArrIndexInput, toArrIndexInput, 
      fromArrIndex, mid
    )
    int right = rangeSumLazyInternal(2 * treeIndex + 2, 
      fromArrIndexInput, toArrIndexInput, 
      mid + 1, toArrIndex
    )
    return left + right;
  }
}

Complexity​

Let's say there are N\text{N} elements in an array.

Time Complexity​

Time complexity for building segment tree is:

O(log N)\text{O(log N)}

Time complexity for point update, range update and range sum is:

O(log N)\text{O(log N)}

Space Complexity​

Segment tree uses two seperate array for storing segment tree and lazy updates, so space complexity is:

O(N)\text{O(N)}

How to Spot These Problems​

You can identify segment tree problems if the problem requires you to:

  • Quickly calculate the sum of elements from the start of an array up to a certain index.

Leetcode Problem Set​