How to implement Fenwick tree?

Question

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 +

Answer 1

https://www.hackerearth.com/practice/notes/binary-indexed-tree-or-fenwick-tree/

I think this will help you.

Answer 2

Zhenis Otarbay

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

Answer 3

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