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/ec31382f4843a582f9fd to your computer and use it in GitHub Desktop.
Save kartikkukreja/ec31382f4843a582f9fd to your computer and use it in GitHub Desktop.
Partial Segment Tree Node
struct SegmentTreeNode {
int start, end; // this node is responsible for the segment [start...end]
// variables to store aggregate statistics and
// any other information required to merge these
// aggregate statistics to form parent nodes
void assignLeaf(InputType value) {
// InputType is the type of input array element
// Given the value of an input array element,
// build aggregate statistics for this leaf node
}
void merge(SegmentTreeNode& left, SegmentTreeNode& right) {
// merge the aggregate statistics of left and right
// children to form the aggregate statistics of
// their parent node
}
OutputType query() {
// OutputType is the type of the required aggregate statistic
// return the value of required aggregate statistic
// associated with this node
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment