segment tree segment sum complexity code example

Example 1: Segment tree

void build(int node, int start, int end)
{
    if(start == end)
    {
        // Leaf node will have a single element
        tree[node] = A[start];
    }
    else
    {
        int mid = (start + end) / 2;
        // Recurse on the left child
        build(2*node, start, mid);
        // Recurse on the right child
        build(2*node+1, mid+1, end);
        // Internal node will have the sum of both of its children
        tree[node] = tree[2*node] + tree[2*node+1];
    }
}

Example 2: 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);
    }
};