How to implement Fenwick tree? | SoloLearn: Learn to code for FREE!

+1

How to implement Fenwick tree?

I don't remember if i described this problem earlier -- we have a set of events (up to 250000 for current project, if we can increase the upper bound it is even better), and a "chance" for each event (double precision floating point value). We need to generate a series of events according to these chances (probability of event i is chance c_i divided by the sum of all chances). The problem is that after each event the "chances" for some (up to 100) events change. It needs to generate around 10^10 events in one day. For now i think that a good approach to this is using a Fenwick tree https://cp-algorithms.com/data_structures/fenwick.html#toc-tgt-10 -- put all the chances in it, than generate a random number in [0, sum_chances) and do binary search (binary search in Fenwick tree can be done in O(n log(n)), if done carefully. There's still a problem with keeping and updating doubles in Fenwick tree -- common implementations accumulate numeric error due to the new values being defined as sum of old_value +

1/17/2021 4:30:59 PM

Zhenis Otarbay

3 Answers

New Answer

+2

https://www.hackerearth.com/practice/notes/binary-indexed-tree-or-fenwick-tree/ I think this will help you.

+1

Zhenis Otarbay I thought that it will be helps you. So I post it

0

Sathe Prerana Satish just from a glance it describes a basic binary indexed tree, so still can have loss of precision for double variables