Codementor Events

Segment Tree or Fenwick Tree?

Published May 22, 2021

Hi Guys ๐Ÿ˜Š
We have given an array arr[1 . . . n]. We would like to
1 Compute the sum of the first i elements.
2 Modify the value of a specified element of the array arr[i] = x where 1 <= i <= n.

A simple solution can be done in O(n) for the first requirement and in O(1) for the second requirement where an index is given and you have to simply update the new value.

๐‚๐š๐ง ๐ฐ๐ž ๐ซ๐ž๐๐ฎ๐œ๐ž ๐ญ๐ก๐ž ๐ญ๐ข๐ฆ๐ž ๐œ๐จ๐ฆ๐ฉ๐ฅ๐ž๐ฑ๐ข๐ญ๐ฒ ๐ญ๐จ ๐š๐œ๐ก๐ข๐ž๐ฏ๐ž ๐ญ๐ก๐ž๐ฌ๐ž ๐ซ๐ž๐ช๐ฎ๐ข๐ซ๐ž๐ฆ๐ž๐ง๐ญ๐ฌ?
Yes, it can be solved in ๐Ž(๐ฅ๐จ๐ ๐ง) by using either Segment tree or Fenwick Tree(Binary Index tree).

๐–๐ก๐š๐ญ ๐ฌ๐ก๐จ๐ฎ๐ฅ๐ ๐ฐ๐ž ๐œ๐ก๐จ๐จ๐ฌ๐ž? ๐’๐ž๐ ๐ฆ๐ž๐ง๐ญ ๐ญ๐ซ๐ž๐ž ๐จ๐ซ ๐…๐ž๐ง๐ฐ๐ข๐œ๐ค ๐ญ๐ซ๐ž๐ž.
We should choose ๐…๐ž๐ง๐ฐ๐ข๐œ๐ค ๐ญ๐ซ๐ž๐ž as it requires less space and easy to implement (only 10 lines of code).here...

Discover and read more posts from Ashay Nayak
get started