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