Structure of Each Node:
struct SegmentTreeNode {
//Information each node contains
void assignLeaf(int value) {
//Intialize each node
}
void merge(SegmentTreeNode& left, SegmentTreeNode& right) {
//Logic to merge the node
}
int getValue() {
//returning the value queried
}
};
struct SegmentTreeNode {
//Information each node contains
void assignLeaf(int value) {
//Intialize each node
}
void merge(SegmentTreeNode& left, SegmentTreeNode& right) {
//Logic to merge the node
}
int getValue() {
//returning the value queried
}
};
Template:
template<class T, class V>
class SegmentTree {
SegmentTreeNode* nodes;
int N;
public:
SegmentTree(T arr[], int N) {
this->N = N;
nodes = new SegmentTreeNode[getSegmentTreeSize(N)];
buildTree(arr, 1, 0, N-1);
}
~SegmentTree() {
delete[] nodes;
}
V getValue(int lo, int hi) {
SegmentTreeNode result = getValue(1, 0, N-1, lo, hi);
return result.getValue();
}
void update(int index, T value) {
update(1, 0, N-1, index, value);
}
private:
void buildTree(T arr[], int stIndex, int lo, int hi) {
if (lo == hi) {
nodes[stIndex].assignLeaf(arr[lo]);
return;
}
int left = 2 * stIndex, right = left + 1, mid = (lo + hi) / 2;
buildTree(arr, left, lo, mid);
buildTree(arr, right, mid + 1, hi);
nodes[stIndex].merge(nodes[left], nodes[right]);
}
SegmentTreeNode getValue(int stIndex, int left, int right, int lo, int hi) {
if (left == lo && right == hi)
return nodes[stIndex];
int mid = (left + right) / 2;
if (lo > mid)
return getValue(2*stIndex+1, mid+1, right, lo, hi);
if (hi <= mid)
return getValue(2*stIndex, left, mid, lo, hi);
SegmentTreeNode leftResult = getValue(2*stIndex, left, mid, lo, mid);
SegmentTreeNode rightResult = getValue(2*stIndex+1, mid+1, right, mid+1, hi);
SegmentTreeNode result;
result.merge(leftResult, rightResult);
return result;
}
int getSegmentTreeSize(int N) {
int size = 1;
for (; size < N; size <<= 1);
return size << 1;
}
void update(int stIndex, int lo, int hi, int index, T value) {
if (lo == hi) {
nodes[stIndex].assignLeaf(value);
return;
}
int left = 2 * stIndex, right = left + 1, mid = (lo + hi) / 2;
if (index <= mid)
update(left, lo, mid, index, value);
else
update(right, mid+1, hi, index, value);
nodes[stIndex].merge(nodes[left], nodes[right]);
}
};
Segment Tree Instance :
Segment Tree intialization
Segmenttree<int,int> s(a,n)
