Segment Tree

In computer science, a segment tree, also known as a statistic tree, is a tree data structure used for storing information about intervals, or segments. It allows querying which of the stored segments contain a given point. It is, in principle, a static structure; that is, it’s a structure that cannot be modified once it’s built. A similar data structure is the interval tree.

A segment tree for a set I of n intervals uses O(n log n) storage and can be built in O(n log n) time. Segment trees support searching for all the intervals that contain a query point in time O(log n + k), k being the number of retrieved intervals or segments.

Implementation

SegmentTree* build(vector<long>& arr, int l, int r) {
    if(l > r) return NULL;
    SegmentTree* sg = new SegmentTree(arr[l], arr[r]);
    if(l == r) return sg;
    int m = l + (r - l) / 2;
    sg->left = build(arr, l, m);
    sg->right = build(arr, m + 1, r);
    return sg;
}
    
struct SegmentTree{
    long mi;
    long ma;
    int count;
    SegmentTree* left;
    SegmentTree* right;
    
    SegmentTree(long l, long r) :mi(l), ma(r), count(0), left(NULL), right(NULL) {}
    
    void update(long n) {
        if(mi > n or ma < n) return;
        count++;
        if(left) left->update(n);
        if(right) right->update(n);
    }
    
    int qry(long lo, long hi) {
        if(mi > hi or ma < lo) return 0;
        if(lo <= mi and ma <= hi) return count;
        return (left ? left->qry(lo,hi) : 0) + (right ? right->qry(lo,hi) : 0);
    }
};