Fenwick-Tree

[kratimitra]

Description of the problem

Hey, I am Krati Mitra (Discord username Krati(P)#8709), a GSSOC'21 participant. I want to add the code for the "Fenwick-Tree " which is an advanced data structure . I can contribute to add this data structure using Python.

Example of the problem

References/Other comments

@czgdp1807, Please assign me this.

[Smit-create]

Hi @kratimitra , Can you show some rough idea of how the class structure will look and what methods will you use in it?

[kratimitra]

Hi @Smit-create Please find below the class structure and the description for this issue.

Fenwick-Tree is an advanced data structure, basically used to store cumulative frequencies Fenwick Tree is represented by an array. Methods that we will be performing using this DS: a) update(index , add) : To update the fenwick tree basically adding a value 'add' to the index and keep on adding it until we reach to all its children. b) sum(index): We can calculate sum of elements till any index (Prefix Sum). The idea is to start with the index and get its value and keep moving to its parent till it is not 0 and keep on adding the value stored in the fenwick tree. c) range_sum(range_l , range_r) : It will be returning the sum of elements between range_l and range_r.

[Smit-create]

Yes, this looks fine. You can raise a PR for that

[czgdp1807]

Note that, we need a n-dimensional Fenwick tree instead of a special case 1D or 2D. You can take ideas from https://cp-algorithms.com/data_structures/fenwick.html#toc-tgt-6 and extend it for n-D. Though if you are not comfortable with generalizing the idea, feel free to email me, I will schedule a meeting for discussion (though do it only if you are very much interested in pursuing this issue). Thanks.

[AbhijitDutta338]

Is the implementation of fenwick tree completed? If not, can I work on it?

[czgdp1807]

You can work on n-dimensional fenwick tree (a.k.a, BinaryIndexedTree). See, pydatastructs/trees/binary_trees.py::BinaryIndexedTree for 2-D fenwick tree.