Partial Segment Tree Template

Partial Segment Tree Template.cpp

template<class InputType, class UpdateType, class OutputType>
class SegmentTree {
  SegmentTreeNode* nodes;
  int N;
    
public:
  SegmentTree(InputType arr[], int N) {
    this->N = N;
    nodes = new SegmentTreeNode[getSegmentTreeSize(N)];
    buildTree(arr, 1, 0, N-1);
  }
  
  ~SegmentTree() {
    delete[] nodes;
  }
  
  // get the value associated with the segment [start...end]
  OutputType query(int start, int end) {
    SegmentTreeNode result = query(1, start, end);
    return result.query();
  }
  
  // range update: update the range [start...end] by value
  // Exactly what is meant by an update is determined by the
  // problem statement and that logic is captured in segment tree node
  void update(int start, int end, UpdateType value) {
    update(1, start, end, value);
  }
  
private:
  void buildTree(InputType arr[], int stIndex, int start, int end) {
    // nodes[stIndex] is responsible for the segment [start...end]
    nodes[stIndex].start = start, nodes[stIndex].end = end;
    
    if (start == end) {
      // a leaf node is responsible for a segment containing only 1 element
      nodes[stIndex].assignLeaf(arr[start]);
      return;
    }
    
    int mid = (start + end) / 2,
        leftChildIndex = 2 * stIndex,
        rightChildIndex = leftChildIndex + 1;
        
    buildTree(arr, leftChildIndex, start, mid);
    buildTree(arr, rightChildIndex, mid + 1, end);
    nodes[stIndex].merge(nodes[leftChildIndex], nodes[rightChildIndex]);
  }
  
  int getSegmentTreeSize(int N) {
    int size = 1;
    for (; size < N; size <<= 1);
    return size << 1;
  }
  
  SegmentTreeNode query(int stIndex, int start, int end) {
    // we'll fill this in later
  }
  
  void update(int stIndex, int start, int end, UpdateType value) {
    // we'll fill this in later
  }
};