codezonediitj / pydatastructs

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

Add lazy segment tree #539

Open sak-codes opened 1 year ago

sak-codes commented 1 year ago

References to other Issues or PRs or Relevant literature

Brief description of what is fixed or changed

Other comments

codecov[bot] commented 1 year ago

Codecov Report

Merging #539 (069b5df) into main (8f419fd) will decrease coverage by 1.743%. Report is 15 commits behind head on main. The diff coverage is 71.014%.

Additional details and impacted files ```diff @@ Coverage Diff @@ ## main #539 +/- ## ============================================= - Coverage 98.528% 96.785% -1.743% ============================================= Files 32 34 +2 Lines 4010 4418 +408 ============================================= + Hits 3951 4276 +325 - Misses 59 142 +83 ``` | [Files Changed](https://app.codecov.io/gh/codezonediitj/pydatastructs/pull/539?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=codezonediitj) | Coverage Δ | | |---|---|---| | [...ucts/miscellaneous\_data\_structures/segment\_tree.py](https://app.codecov.io/gh/codezonediitj/pydatastructs/pull/539?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=codezonediitj#diff-cHlkYXRhc3RydWN0cy9taXNjZWxsYW5lb3VzX2RhdGFfc3RydWN0dXJlcy9zZWdtZW50X3RyZWUucHk=) | `82.327% <70.542%> (-14.869%)` | :arrow_down: | | [...tructs/miscellaneous\_data\_structures/algorithms.py](https://app.codecov.io/gh/codezonediitj/pydatastructs/pull/539?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=codezonediitj#diff-cHlkYXRhc3RydWN0cy9taXNjZWxsYW5lb3VzX2RhdGFfc3RydWN0dXJlcy9hbGdvcml0aG1zLnB5) | `94.000% <77.777%> (-0.792%)` | :arrow_down: | ... and [14 files with indirect coverage changes](https://app.codecov.io/gh/codezonediitj/pydatastructs/pull/539/indirect-changes?src=pr&el=tree-more&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=codezonediitj) [![Impacted file tree graph](https://app.codecov.io/gh/codezonediitj/pydatastructs/pull/539/graphs/tree.svg?width=650&height=150&src=pr&token=mZMqq5ubAu&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=codezonediitj)](https://app.codecov.io/gh/codezonediitj/pydatastructs/pull/539?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=codezonediitj)
sak-codes commented 1 year ago

I am trying to design the method parameters such that I can generalize the implementation but since lazy updates for each of the different applications have different implementation, I am unable to find a common design.

czgdp1807 commented 1 year ago

lazy updates for each of the different applications have different implementation, I am unable to find a common design.

Share some examples so that we can figure something out.

sak-codes commented 1 year ago

Suppose we are solving an range sum update problem where we want to increment all the elements in the range $[i, j]$ with some number x. This is okay and well generalized for j != i. But when we want to change some element at index $i$, then if we use the same above approach then we need to pass by y=x-cur_value[i], then during the update we will have cur_value[i] += y. So user will get confuse when to use y and when to use x.

sak-codes commented 1 year ago

So you want me to rename update_range to update?