Segment Tree or Fenwick Tree?
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...