Add Segment Trees

[czgdp1807]

Description of the problem

Add segment trees to pydatastructs.trees.space_partitioning_trees.

Example of the problem

References/Other comments

Use, https://en.wikipedia.org/wiki/Segment_tree

[czgdp1807]

I am working on it.

[Smit-create]

Can we also add update operation? As I think this is the most necessary feature for which segment tree is used as it can update the interval list in O(logN) time. That is segment tree are generally used to solve online problems (real time update and queries). Moreover, without this update operation, quering on just given set of segments there exits O(1) technique(using prefix sums which build in O(MAXN) and each query in O(1))

[czgdp1807]

It is, in principle, a static structure; that is, it's a structure that cannot be modified once it's built. A similar data structure is the interval tree.

From wikipedia. So, for dynamic segment trees we should subclass SegmentTree in DynamicSegmentTree and add an update method to it. Another question is how will the algorithm for updating segment tree will work, especially the ones defined here.

[aman503]

Can I work on this issue?

[Rajveer100]

I can work on the issue..
I have so many templates..you can check in my GitHub..C++ -> Python I will do the implementation and conversion..

[czgdp1807]

Sure. Please read the above comments before starting.

[Rajveer100]

Hello @czgdp1807,

I have completed the implementation of Segment Tree with rangeQuery, rangeUpdate, pointUpdate, and all operations in O(log(n)) time...Here is my code...

Many more things like min, max, gcd, etc can be added just by changing the default values to respective ones..which I will make it in the template itself for ease of use...

This was to just update you..that most part is finished..Just need your suggestions and recommendations..Thank You.

(Also, forgot to mention, I am taking part in GSSOC 2022...as well..)
👍

Here is my code :

It is committed under the branch "origin_user"..and have also done the PR...Waiting for your approval...

[Rajveer100]

Could you please checkout the above message so that I can make the changes if required...Thank you...

[czgdp1807]

@Rajveer100 Please feel free to open a PR. I will review there. Thanks.

[Rajveer100]

Yes I have already done the PR(483)..Thank you so much for your reply..