pydatastructs
pydatastructs copied to clipboard
codezonediitj
Add Segment Trees
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
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))
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.
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..
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...
Could you please checkout the above message so that I can make the changes if required...Thank you...