segment tree deletion time complexity code example

Example: segment tree complexity

class SegmentTree{
public:
    vector<int> segv;
    int n;
    SegmentTree(vector<int> &nums) {
        if (!nums.size()) return ;
        segv.assign(nums.size() * 4, 0);
        n = nums.size();
        build(nums, 1, 0, n - 1); 
    }
    void build(vector<int> &nums, int v, int l, int r) {
        if (l == r) segv[v] = nums[l];
        else {
            int mid = l + (r - l) / 2;
            build(nums, v * 2, l, mid);
            build(nums, v * 2 + 1, mid + 1, r);
            segv[v] = segv[v * 2] + segv[v * 2 + 1]; 
        }
    }
    int sumRange(int v, int l, int r, int a, int b) {
        if (a > b) return 0;
        if (l == a && r == b) return segv[v];
        int mid = l + (r - l) / 2;
        return sumRange(v * 2, l, mid, a, min(mid, b))
            + sumRange(v * 2 + 1, mid + 1, r, max(mid + 1, a), b);
    }
    void update(int v, int l, int r, int pos, int val) {
        if (l == r) segv[v] = val;
        else {
            int mid = l + (r - l) / 2;
            if (pos <= mid) update(v * 2, l, mid, pos, val);
            else update(v * 2 + 1, mid + 1, r, pos, val);
            segv[v] = segv[v * 2] + segv[v * 2 + 1];
        }
    }
    int sumRange(int a, int b) {
        return sumRange(1, 0, n - 1, a, b);
    }
    void update(int pos, int val) {
        update(1, 0, n - 1, pos, val);
    }
};

Tags:

Misc Example