GSS4 update()

GSS4 update().cpp

void update(int stIndex, int start, int end, UpdateType value) {
  if (nodes[stIndex].start == start && nodes[stIndex].end == end) {
    lazyPropagatePendingUpdateToSubtree(stIndex, value);
    return;
  }
    
  int mid = (nodes[stIndex].start + nodes[stIndex].end) >> 1,
      leftChildIndex = stIndex << 1,
      rightChildIndex = leftChildIndex + 1;
      
  if (start > mid)
    update(rightChildIndex, start, end, value);
  else if (end <= mid)
    update(leftChildIndex, start, end, value);
  else {
    update(leftChildIndex, start, mid, value);
    update(rightChildIndex, mid+1, end, value);
  }
  nodes[stIndex].merge(nodes[leftChildIndex], nodes[rightChildIndex]);
}

void lazyPropagatePendingUpdateToSubtree(int stIndex, UpdateType value) {
  nodes[stIndex].addUpdate(value);
  if (!nodes[stIndex].isPropagationRequired())
    return;
      
  if (nodes[stIndex].start == nodes[stIndex].end) {
    nodes[stIndex].applyPendingUpdate();
    return;
  }
  
  UpdateType pendingUpdate = nodes[stIndex].getPendingUpdate();
  nodes[stIndex].clearPendingUpdate();
  int mid = (nodes[stIndex].start + nodes[stIndex].end) >> 1,
      leftChildIndex = stIndex << 1,
      rightChildIndex = leftChildIndex + 1;
          
  lazyPropagatePendingUpdateToSubtree(leftChildIndex, pendingUpdate);
  lazyPropagatePendingUpdateToSubtree(rightChildIndex, pendingUpdate);        
  nodes[stIndex].merge(nodes[leftChildIndex], nodes[rightChildIndex]);
}