# Fenwick Tree

## Complexity:

Element Update: O(log N)

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)

• 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.

--

--