Segment Tree Problem

class SegmentTree {
    vector<int> tree;
    int n;

    void build(const vector<int>& nums, int root, int left, int right){
        if(left == right){
            tree[root] = nums[left];
            return;
        }

        int mid = left + (right - left) / 2;
        build(nums, 2 * root + 1, left, mid);
        build(nums, 2 * root + 2, mid+1, right);

        tree[root] = tree[2 * root + 1] + tree[2 * root + 2];
    }
    
    int rangeQuery(int root, int left, int right, int ql, int qr){
        if(qr < left || ql > right) return 0; // no overlap
        if(ql <= left && qr >= right) return tree[root]; // complete overlap

        // partial overlap
        int mid = left + (right - left) / 2;
        int leftSum = rangeQuery(2 * root + 1, left, mid, ql, qr);
        int rightSum = rangeQuery(2 * root + 2, mid + 1, right, ql, qr);
        return leftSum + rightSum;
    } 
    void pointUpdate(int root, int left, int right, int idx, int val){
        if(left == right){
            tree[root] = val;
            return;
        }
        int mid = left + (right - left) / 2;
        if(idx <= mid){
            pointUpdate(2 * root + 1, left, mid, idx, val);
        }
        else{
            pointUpdate(2 * root + 2, mid + 1, right, idx, val);
        }
        tree[root] = tree[2 * root + 1] + tree[2 * root + 2];
    }


public:

    SegmentTree(const vector<int>& nums){
        n = nums.size();
        tree.resize(4 * n, 0);
        build(nums, 0, 0, n-1);
        
    }

    int query(int ql, int qr){
        return rangeQuery(0, 0, n-1, ql, qr);
    }   
    void update(int idx, int val){
        pointUpdate(0, 0, n-1, idx, val);
    }  
};

Input:
6
1 3 5 7 9 11
7
q 0 2
q 1 3
u 1 10
q 0 2
q 1 3
q 0 0
q 5 5

Output:
9
15
16
22
1
11

class SegmentTree{
    vector<int> tree;
    int n;

    void build(const vector<int> &nums, int root, int left, int right){
        if(left == right) {
            tree[root] = nums[left];
            return;
        }

        int mid = left + (right - left) / 2;
        build(nums, 2 * root + 1, left, mid);
        build(nums, 2 * root + 2, mid + 1, right);

        tree[root] = min(tree[2 * root + 1], tree[2 * root + 2]);
    }

    int query(int root, int left, int right, int ql, int qr){
        // out bound (no overlap)
        if(qr < left || ql > right) return INT_MAX;

        // complete overlap
        if(ql <= left && qr >= right) return tree[root];

        // partial overlap
        int mid = left + (right - left) / 2;
        int leftMin = query(root * 2 + 1, left, mid, ql, qr);
        int rightMin = query(root * 2 + 2, mid + 1, right, ql, qr);

        return min(leftMin, rightMin);
    }

    void pointUpdate(int root, int left, int right, int index, int value){
        if(left == right){
            tree[root] = value;
            return;
        }

        int mid = left + (right - left) / 2;
        if(index <= mid){
            pointUpdate(root * 2 + 1, left, mid, index, value);
        }
        else{
            pointUpdate(root * 2 + 2, mid + 1, right, index, value);
        }

        tree[root] = min(tree[root * 2 + 1], tree[root * 2 + 2]);
    }
    
public:
    SegmentTree(const vector<int> &nums){
        this->n = nums.size();
        tree.resize(n * 4);
        build(nums, 0, 0, n-1);
    }

    int rangeMin(int left, int right){
        return query(0, 0, n-1, left, right);
    }

    void update(int index, int value){
        pointUpdate(0, 0, n-1, index, value);
    }
};

Input:
6
4 2 5 1 9 3
5
1 0 3
2 2 0
1 0 3
2 4 6
1 3 5

Output:
1
0
1

class SegmentTree{
    vector<unordered_map<int, int>> tree;
    int n;

    void mergeLeftRight(int root){
        tree[root].clear();
        for(const auto &[num, freq] : tree[2 * root + 1]){
            tree[root][num] += freq;
        }

        for(const auto &[num, freq] : tree[2 * root + 2]){
            tree[root][num] += freq;
        }
    }

    void build(const vector<int> &nums, int root, int left, int right){
        if(left == right){
            int num = nums[left];
            tree[root][num] = 1;
            return;
        }
        int mid = left + (right - left) / 2;
        build(nums, 2 * root + 1, left, mid);
        build(nums, 2 * root + 2, mid + 1, right);

        mergeLeftRight(root);
    }

    void pointUpdate(int root, int left, int right, int index, int val){
        if(left == right){
            tree[root].clear();
            tree[root][val] = 1;
            return;
        }

        int mid = left + (right - left) / 2;
        if(index <= mid){
            pointUpdate(2*root + 1, left, mid, index, val);
        }
        else{
            pointUpdate(2* root + 2, mid + 1, right, index, val);
        }

        mergeLeftRight(root);
    }

    int query(int root, int left, int right, int ql, int qr, int k){
        if(qr < left || ql > right) return 0; // no overlap
        if(ql <= left && qr >= right){ // complete overlap
            return tree[root][k];
        }

        // partial overlap
        int mid = left + (right - left) / 2;
        int leftCount = query(2 * root + 1, left, mid, ql, qr, k);
        int rightCount = query(2 * root + 2, mid + 1, right, ql, qr, k);

        return leftCount + rightCount;
    }
public:
    SegmentTree(const vector<int> &nums){
        this->n = nums.size();
        tree.resize(4 * n);
        build(nums, 0, 0, n-1);
    }

    void update(int index, int val){
        pointUpdate(0, 0, n-1, index, val);
    }

    int countFreq(int left, int right, int k){
        return query(0, 0, n-1, left, right, k);
    }
};

Input:
7
1 3 1 2 1 3 2
5
2 0 6 1
2 2 4 3
2 1 5 2
1 3 3
2 0 6 3

Output:
3
0
1
3

class SegmentTree
{
    vector<int> tree;
    vector<int> lazyTree;
    int n;

    void build(const vector<int> &nums, int root, int left, int right)
    {
        if (left == right)
        {
            tree[root] = nums[left];
            return;
        }

        int mid = left + (right - left) / 2;
        build(nums, root * 2 + 1, left, mid);
        build(nums, root * 2 + 2, mid + 1, right);

        tree[root] = tree[root * 2 + 1] + tree[root * 2 + 2];
    }

    void propogate(int root, int left, int right){
        if(lazyTree[root] == 0) return;

        tree[root] += (right - left + 1) * lazyTree[root];
        if(left != right){ // non leaf node
            lazyTree[root * 2 + 1] += lazyTree[root];
            lazyTree[root * 2 + 2] += lazyTree[root];
        }
        lazyTree[root] = 0;
    }

    void update(int root, int left, int right, int ql, int qr, int val)
    {
        propogate(root, left, right);
        
        if(ql > right || qr < left) return; // no overlap
        if(ql <= left && qr >= right){ // complete overlap
            lazyTree[root] = val;
            propogate(root, left, right);
            return;
        }

        //partial overlap
        int mid = left + (right - left) / 2;
        update(root * 2 + 1, left, mid, ql, qr, val);
        update(root * 2 + 2, mid + 1, right, ql, qr, val);
        
        tree[root] = tree[root * 2 + 1] + tree[root * 2 + 2];
    }

    int query(int root, int left, int right, int ql, int qr)
    {
        propogate(root, left, right);
        if(ql > right || qr < left) return 0; // no overlap
        if(ql <= left && qr >= right) return tree[root];

        //partial update
        int mid = left + (right - left) / 2;
        int leftSum = query(root * 2 + 1, left, mid, ql, qr);
        int rightSum = query(root * 2 + 2, mid + 1, right, ql, qr);

        return leftSum + rightSum;
    }

public:
    SegmentTree(const vector<int> &nums)
    {
        this->n = nums.size();
        tree.resize(n * 4, 0);
        lazyTree.resize(n * 4, 0);
        build(nums, 0, 0, n - 1);
    }

    int rangeSum(int left, int right)
    {
        return query(0, 0, n - 1, left, right);
    }

    void rangeUpdate(int left, int right, int value)
    {
        update(0, 0, n - 1, left, right, value);
    }
};

Input:
5
0 0 0 0 0
6
2 1 3 5
1 0 4
2 0 2 2
1 0 2
1 3 4
1 1 1

Output:
15 16 5 7