Added `ArraySegmentTree` and `RangeQueryDynamic`

[Rajveer100]

Added Segment Trees with Lazy Propagation :

Functions : RangeQuery, RangeUpdate, PointUpdate...(O(log(n)) time..

Will be further adding more additions for better user experience...

[czgdp1807]

I would name it as DynamicSegmentTree and keep it in a new file, miscellaneous_data_structures/dynamic_segment_tree.py. In addition, please care to add some tests and documentation strings. Take some time to understand the coding pattern inside the project before adding your code.

[Rajveer100]

Thank you for your feedback..I will make these changes..as soon as possible to make it more readable and clean... 👍

[Rajveer100]

Hello @czgdp1807, I have added all necessary DocStrings with examples and test cases for using the data structure...And have also placed it in the right folder [miscellaneous data structures] as you mentioned..

I request you to review my updated code which I have committed..

[czgdp1807]

Overall, you have worked hard on it. Though, have you included n-dimensional segment trees? I think that would make this feature applicable to a lot more use cases.

[Rajveer100]

Overall, you have worked hard on it. Though, have you included n-dimensional segment trees? I think that would make this feature applicable to a lot more use cases.

Thank you so much for your respect...I haven't added n-dimensional tree yet..and I actually request you to give me little time for that..but would be obliged..if you could merge my project after I add the test cases and also make the changes as you mentioned above and then after that I will add that feature as well and will update it from time to time...Thank You..Will commit the changes as you said above..

[Rajveer100]

Please review the changes...will add the changes to test files as well..

[czgdp1807]

The code looks really good. Can you make changes to the tests as well in a similar manner (as we discussed on our call)?

@Smit-create Can you please check the implementation for correctness? Any API suggestions from your experience?

[Rajveer100]

Added the updated tests..as well...please review it.

[Rajveer100]

Corrected header file directory...Please check the commit..

[Rajveer100]

Could you review it, I have corrected the white spaces and new line error...

[czgdp1807]

I will review tomorrow.

[czgdp1807]

Hi. Please be patient. Meanwhile, feel free to start working on another feature. :-)

[codecov[bot]]

Codecov Report

Merging #483 (551e58d) into master (8c91a6a) will decrease coverage by 0.070%. The diff coverage is 96.794%.

@@              Coverage Diff              @@
##            master      #483       +/-   ##
=============================================
- Coverage   98.594%   98.523%   -0.071%     
=============================================
  Files           30        31        +1     
  Lines         3841      3996      +155     
=============================================
+ Hits          3787      3937      +150     
- Misses          54        59        +5     

Impacted Files	Coverage Δ
...ucts/miscellaneous_data_structures/sparse_table.py	97.142% <ø> (ø)
...tructs/miscellaneous_data_structures/algorithms.py	94.791% <95.744%> (+0.791%)	:arrow_up:
...ucts/miscellaneous_data_structures/segment_tree.py	97.196% <97.196%> (ø)
...astructs/miscellaneous_data_structures/__init__.py	100.000% <100.000%> (ø)

[czgdp1807]

Now, we need to add RangeQueryDynamic and RangeQueryDynamicOneDimensionalArraySegmentTree in pydatastructs/miscellaneous_data_structures/algorithms.py.

Lazy propagation can be added afterwards by adding a new class, something like, OneDimensionalArraySegmentTreeWithLazyPropagation. The reason is simple, we would need a new kind of node, i.e., LazyTreeNode which would have an attribute to store whether this node is required to be updated. I would recommend doing this in a follow up PR.

[Rajveer100]

Could you explain me in detail, of all the changes you did above..as it was quite a lot..

[Rajveer100]

Have gone through the commits..but I needed your words..

[czgdp1807]

I decoupled the interface and the implementation of segment trees. Basically, segment trees with range updates need to track some extra information and require extra memory, so it would be better to add them separately in a follow up PR. Storing segment trees in arrays would require 4*N sized array which is too much provided the number of nodes are always constant in a segment tree.

[Rajveer100]

My segment tree takes 2N memory...not 4N typical implementation...anyway..I guess you wanted to completely reorganise the interface..so I will make the commits and changes respectively..

[Rajveer100]

Also, what about the previous implementation, which I initially made..so now that's not required anymore (other than reference) ?

[czgdp1807]

so now that's not required anymore (other than reference)

Yes, not required anymore.

[Rajveer100]

Now, we need to add RangeQueryDynamic and RangeQueryDynamicOneDimensionalArraySegmentTree in pydatastructs/miscellaneous_data_structures/algorithms.py.

Lazy propagation can be added afterwards by adding a new class, something like, OneDimensionalArraySegmentTreeWithLazyPropagation. The reason is simple, we would need a new kind of node, i.e., LazyTreeNode which would have an attribute to store whether this node is required to be updated. I would recommend doing this in a follow up PR.

So now I have to do this right?

[czgdp1807]

You can if you want to.

[czgdp1807]

In a follow up PR add, both the new APIs to docs.

[Rajveer100]

Hey Thanks...alot..meanwhile I am working on order statistic and interval trees also..Will commit them under their PRs..

[czgdp1807]

order statistic

Could you please provide a reference for this?

[Rajveer100]

order statistic

Could you please provide a reference for this?

It's basically a self balancing tree like RB, AVL, B, van-embde-boas, etc...In the augmented form..where we stored two bits of extra information...for fetching osrank and osselect operations...please refer my C++ implementation for the same under "My Templates repo"...and here is a link for more info:

(CLRS pdf) https://edutechlearners.com/download/Introduction_to_algorithms-3rd%20Edition.pdf

See the augmenting data structures part...before which red black trees is also given...

[czgdp1807]

Can you check if is_order_statistic, select(i) in https://pydatastructs.readthedocs.io/en/latest/pydatastructs/trees/binary_trees.html matches what you are trying to add?

[Rajveer100]

Yes it matches...but you have used AVL trees in your implementation?

[czgdp1807]

No. Any tree class can call select. Its generic. See the inheritance pattern. I think order statistic feature is already there. You can go ahead with interval trees though.

[Rajveer100]

So I think that I will start doing interval trees?...Since the repo already contains order statistic..And also this would be kinda nice...to have both kinds of trees...generally speaking RB Trees are most general and efficient also used in C++, Java..and their implementations of their DS..

[Rajveer100]

Cool...So I will get back to you directly under that issue..