Skip to content

Instantly share code, notes, and snippets.

@kartikkukreja
Last active August 29, 2015 14:13
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save kartikkukreja/d4f5bc43b4774e2ffe97 to your computer and use it in GitHub Desktop.
Save kartikkukreja/d4f5bc43b4774e2ffe97 to your computer and use it in GitHub Desktop.
GSS4 SegmentTreeNode
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;
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment