Segment Tree/Fenwick Tree

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

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store