search

codezonediitj / pydatastructs

A python package for data structures and algorithms
https://pydatastructs.readthedocs.io/en/stable/
Other
201 stars 269 forks source link

Add Segment Trees #6

Open czgdp1807 opened 5 years ago

czgdp1807 commented 5 years ago

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 commented 5 years ago

I am working on it.

Smit-create commented 3 years ago

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 commented 3 years ago

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 commented 3 years ago

Can I work on this issue?

Rajveer100 commented 2 years ago

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 commented 2 years ago

Sure. Please read the above comments before starting.

Rajveer100 commented 2 years ago

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 commented 2 years ago

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

czgdp1807 commented 2 years ago

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

Rajveer100 commented 2 years ago

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