GSS4 SegmentTreeNode

GSS4 SegmentTreeNode.cpp

struct SegmentTreeNode {
  int start, end; // this node is responsible for the segment [start...end]
  ll total;
  bool pendingUpdate;
  
  SegmentTreeNode() : total(0), pendingUpdate(false) {}
  
  void assignLeaf(ll value) {
    total = value;
  }
  
  void merge(SegmentTreeNode& left, SegmentTreeNode& right) {
    total = left.total + right.total;
  }
  
  ll query() {
    return total;
  }
  
  // For this particular problem, propagation is not required
  // if all elements in this segment are 1's
  bool isPropagationRequired() {
    return total > end-start+1;
  }
  
  void applyPendingUpdate() {
    total = (ll) sqrt(total);
    pendingUpdate = false;
  }
  
  // For this particular problem, the value of the update is dummy
  // and is just an instruction to square root the leaf value
  void addUpdate(bool value) {
    pendingUpdate = true;
  }
  
  // returns a dummy value
  bool getPendingUpdate() {
    return true;
  }
  
  void clearPendingUpdate() {
    pendingUpdate = false;
  }
};