Segment Tree/Fenwick Tree

These data structures are similar in the sense they can be used for range or interval based querying operations but can handle updates to array in Log(n) time. Hence these trees are faster than using normal arrays.

Fenwick Tree

Complexity:

Element Update: O(log N)

Construction/Pre-Processing: O(N log N)

Points to remember:

1. The index in fenwick tree starts with 1 .
2. To construct/update , we keep setting the right bit and adding it up
3. To query we propagate downwards by turning off the left most bits

Segment Tree

Complexity:

Element Update: O(log N)

Construction/Pre-Processing : O(n)

Points to remember:

• We would just 2*n of the space to construct a segment tree.
• In the below algorithm, all contents get shifted by 1 to left , empty space is left at the end
• for update — it is similar to binary srch find and a merge
• for querying — we have edge conditions , we check if the current bound fully covers the req bound, then we fully go left or right and then finally we try both left and right and then merge
• for construction — we follow plain binary search and merge
• all of the above have the if lo==hi condition and a merge operation

Iterative (Easier) version of Segment Tree

• To build the segtree, first fill all the n+1 to 2*n-1 elements with the original array
• Now compute the parent as tree[i]=tree[2*i]+tree[2*i+1]

void buildseg(vector<int>&v,vector<int>&tree)
    {
        //fill the end "n" elements in the tree with the original array
         for (int i = n, j = 0;  i < 2 * n; i++,  j++)
            tree[i] = v[j];
        for (int i = n - 1; i > 0; --i)
            tree[i] = tree[i * 2] + tree[i * 2 + 1];       
    }

• To update the segtree, make sure the left is always even and the right is always odd , now tree[pos/2]=tree[left]+tree[right]. Continue till pos>0

void updateseg(int pos,int val)
    {
        
        pos += n;
        tree[pos] = val;
        while (pos > 0) {
            int left = pos;
            int right = pos;
            if (pos % 2 == 0) {
                right = pos + 1;
            } else {
                left = pos - 1;
            }
            // parent is updated after child is updated
            tree[pos / 2] = tree[left] + tree[right];
            pos /= 2;
        }        
    }

• To query on the seg tree, move the indices to the leaf (add n to the left and right indices)and start adding up to the parents
• Now perform the same as update , make sure the left is always even and the right is always off, add the tree[left] and tree[right] to the sum
• Continue the while loop, till you are in the range

int sumRange(int l, int r) {
         l += n;
        // get leaf with value 'r'
        r += n;
        int sum = 0;
        while (l <= r) {
            if ((l % 2) == 1) {
               sum += tree[l];
               l++;
            }
            if ((r % 2) == 0) {
               sum += tree[r];
               r--;
            }
            l /= 2;
            r /= 2;
        }
        return sum;
    }

Difference between Fenwick Tree and Segment Tree

• Segment tree requires more space than fenwick tree
• Binary indexed tree stores items-count per index, and optimized for “how many items are there between index m and n” queries and are strictly index dependent.
• Segment tree stores intervals, and optimized for “which of these intervals contains a given point” queries.

Reference:

1. https://www.youtube.com/watch?v=uSFzHCZ4E-8 (fenwick tree)
2. https://www.youtube.com/watch?v=xztU7lmDLv8 (segment tree)
3. https://leetcode.com/articles/a-recursive-approach-to-segment-trees-range-sum-queries-lazy-propagation/
4. https://cp-algorithms.com/sequences/rmq.html