Segment Tree Implementation - Algorithm Explained and C++ Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

// Find the minimum number for the array between indices L and R, inclusive.
function RangeMinimumQuery(array, L, R) 
  {
  // Initialize the min to be some huge number.
  minNumSoFar = someReallyBigNumber;

  // Search through each number between (and including) L and R
  for(index i = L; i <= R; i++)
    {
    currNum = array[i];
    
    // If the current number is the smallest we've seen so far, use it.
    if(currNum < minNumSoFar)
      { minNumSoFar = currNum; }
    }

  return minNumSoFar;
  }

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

function CreateEmptySTArray(originalArrayLength)
  {
  // Calculate the height of the tree (minus one).
  stHeight = ceil(log2(originalArrayLength));
  
  // Calculate the maximum number of leaves a tree of this height can have.
  maxNumLeaves = (2 * (2 ^ stHeight)) - 1;
  
  // Create an array of that size.
  return array[maxNumLeaves];
  }

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

function RecursivelyFillMin(nodeIndex, nodeStartIndex, nodeEndIndex)
  {
  // If the range is one element long, it only has 
  // one possible choice for the min. Fill the node.
  if(nodeStartIndex == nodeEndIndex)
    {
    value = originalArray[nodeStartIndex];
    stArray[nodeIndex] = value;
    
    // Return this value back up to the caller.
    return value;
    }
    
  // Otherwise, find the minimum by recursively 
  // asking this node's children.
  middleIndex = nodeStartIndex + ((nodeEndIndex - nodeStartIndex) / 2);
  
  leftChildNodeIndex = 2 * nodeIndex;
  rightChildNodeIndex = 2 * nodeIndex + 1;
  
  leftChildMin = RecursivelyFillMin(leftChildNodeIndex, nodeStartIndex, middleIndex);
  rightChildMin = RecursivelyFillMin(rightChildNodeIndex, middleIndex + 1, nodeEndIndex);
  
  minOfThisNode = min(leftChildMin, rightChildMin);
  
  stArray[nodeIndex] = minOfThisNode;
  
  return minOfThisNode;
  }
  
function FillST()
  {
  // Starting with node 0 (the root), covering its entire range, recursively fill the stArray with its values.
  RecursivelyFillMin(0, 0, originalArrayLength - 1);
  
  // After the recursive call (by this line), stArray will be filled.
  }

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

function RecursivelySearchForMin(L, R, nodeIndex, nodeStartIndex, nodeEndIndex)
  {
  // If this node's range is anywhere outside of [L, R]
  // then  don't use it's value. Just return some 
  // really big number (which wouldn't be taken as the minimum).
  if(nodeEndIndex < L || R < nodeStartIndex)
    { 
    return reallyBigNumber;
    }
  
  // If this node is completely within [L, R], 
  // then return it as the min value.
  if(L <= nodeStartIndex && nodeEndIndex <= R)
    {
    return stArray[nodeIndex];
    }
    
  // Otherwise this node is partially within [L, R].
  // (Recursively) check this node's children and return the min of those two.
  middleIndex = nodeStartIndex + ((nodeEndIndex - nodeStartIndex) / 2);
  
  leftChildNodeIndex = 2 * nodeIndex;
  rightChildNodeIndex = 2 * nodeIndex + 1;
  
  leftChildMin = RecursivelySearchForMin(L, R, leftChildNodeIndex, nodeStartIndex, middleIndex);
  rightChildMin = RecursivelySearchForMin(L, R, rightChildNodeIndex, middleIndex + 1, nodeEndIndex); 
  
  minOfThisNode = min(leftChildMin, rightChildMin);
  
  return minOfThisNode;
  }
  
// Find the minimum value between indices L and R.
function FindMin(L, R)
  {
  // Recursively search the tree, starting from the root (node 0).
  min = RecursivelySearchForMin(L, R, 0, 0, origArrayLength - 1);
  
  return min;
  }

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

function RecursivelyUpdateST(newValue, newValueIndex, nodeIndex, nodeStartIndex, nodeEndIndex)
  {
  // If the start index equals the end index, then this node represents the exact value from the original array.
  // We must update this value with the new value (since the old one got replaced).
  if(nodeStartIndex == nodeEndIndex)
    {
    stArray[nodeIndex] = newValue;
    return;
    }
    
  // Otherwise, if check either the left or right subtree to find the index that got updated.
  middleIndex = nodeStartIndex + ((nodeEndIndex - nodeStartIndex) / 2);
  
  leftChildNodeIndex = 2 * nodeIndex;
  rightChildNodeIndex = 2 * nodeIndex + 1;
  
  // If the updated index is in the left subtree...
  if(nodeStartIndex <= newValueIndex && newValueIndex <= middleIndex)
    {
    // Recursively update left subtree.
    RecursivelyUpdateST(newValue, newValueIndex, leftChildNodeIndex, nodeStartIndex, middleIndex);
    }
  // If it's not in the left, then update the right subtree, instead.
  else
    {
    // Recursively update right subtree.
    RecursivelyUpdateST(newValue, newValueIndex, rightChildNodeIndex, middleIndex + 1, nodeEndIndex);
    }
    
  // We can look for the children's min's directly from the ST.
  minFromLeftChild = stArray[leftChildNodeIndex];
  minFromRightChild = stArray[rightChildNodeIndex];
    
  // The min of this node is the min between its two children. 
  // (One of which might have been updated.)
  minOfThisNode = min(minFromLeftChild, minFromRightChild);
  
  stArray[nodeIndex] = minOfThisNode;
  }

function UpdateValue(newValue, newValueIndex)
  {
  // Recursively go through the tree starting at the root (node 0), 
  // and check if any nodes (within this newValue index's range)
  // need to be updated because the newValue is the new minimum for it.
  RecursivelyUpdateST(newValue, newValueIndex, 0, 0, origArrayLength - 1);
  }

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

namespace srcmake {
  ////////////////////////////////////////////////////////////
  /////////// SegmentTree Class Definition ///////////////////
  template<class T>
  class SegmentTree
    {
    private:
      T* st;  // A pointer to the root of the ST.
      int stArrayLength;  // The length of the st array. (Num leaves.)
      int originalArrayLength;  // The length of the original array.
      void AllocateEmptyST(const std::vector<T>&);  // Allocate the space for an empty ST.
      void DeallocateST();  // Delete the ST previously created.
      void FillInST(const std::vector<T>&);// Fill the ST with the proper values.
      T RecursivelyFillST(int, int, int, const std::vector<T>&);   // Recursively find, set, return min of node.
      T RecursivelySearchForMin(int, int, int, int, int);  // Recursively search a node from L to R for it's children's min values (if necessary).
      void RecursivelyUpdate(int, T, int, int, int);  // Recursively update a node with the newValue if it's within the node's range.

    public:
      SegmentTree(std::vector<T>);  // Constructor
      ~SegmentTree();  // Destructor
      T query(int, int);  // Query a range from L to R.
      void update(int, T);  // Update an index to the new value T.
      void print();  // Print the current segment tree (in-order).
    }; // class SegmentTree
  ////////////////////////////////////////////////////////////
  ////////////////////////////////////////////////////////////
} // namespace srcmake

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

// Copyright srcmake 2019.
#include <iostream>
#include <vector>
#include "segment-tree.hpp"

using namespace std;

int main()
  {
  cout << "Program started.\n";

  ////////////////////////////////////////////////////////////
  // Our initial range.
  vector<int> v2 = { 2, 8, 5, 3, 9, 4, 1 };

  // Instantiate our segment tree data structure.
  srcmake::SegmentTree<int> srcmakeSegmentTree2 = srcmake::SegmentTree<int>(v2);
  
  // Print the tree (in-order heap version) so we can see it.
  srcmakeSegmentTree2.print();

  // An example query.
  int L = 0;
  int R = 6;
  cout << "Min from " << L << " to " << R << " is " << srcmakeSegmentTree2.query(L, R) << ".\n";

  ////////////////////////////////////////////////////////////
  
  cout << "Program finished.\n";
  }