Uh oh!
There was an error while loading.Please reload this page.
- Notifications
You must be signed in to change notification settings - Fork1.9k
Added 1-based indexing approach in fenwick tree#1376
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to ourterms of service andprivacy statement. We’ll occasionally send you account related emails.
Already on GitHub?Sign in to your account
base:main
Are you sure you want to change the base?
Uh oh!
There was an error while loading.Please reload this page.
Conversation
jxu commentedOct 21, 2024
Btw you do not need to open a new PR. If you update your branch it will show in the PR. |
urabhay10 commentedOct 21, 2024
Sorry, I am new to open source and I understood my previous PR was full of mistakes so I reopened a new PR |
urabhay10 commentedOct 21, 2024 • edited
Loading Uh oh!
There was an error while loading.Please reload this page.
edited
Uh oh!
There was an error while loading.Please reload this page.
Also, the PR tests failed because of naming convention change it imported the wrong function to check, I've tried to fix that please re run the tests@jxu and check if this PR can be merged. Thank you |
urabhay10 commentedOct 22, 2024
@jxu Could you please review my changes and test my code if it is fit to merge |
urabhay10 commentedOct 24, 2024
@adamant-pwn Can you please review my pull request |
urabhay10 commentedOct 29, 2024
@adamant-pwn Can you please review my request? |
adamant-pwn commentedOct 30, 2024
Hi, this is a brief non-update. Yes, I will look into this, but it might take a bit more time. |
urabhay10 commentedOct 30, 2024
No problem |
jxu commentedNov 4, 2024
Off-topic: we should mention the Fenwick tree was actually first proposed by Boris Ryabko in 1989. It was published in Russian inSoviet Math. Doklady which is probably why it wasn't picked up. |
| **Note:** The Fenwick tree presented here uses zero-based indexing. | ||
| Many people use a version of the Fenwick tree that uses one-based indexing. | ||
| As such, you will also find an alternative implementation which uses one-based indexing in the implementation section. | ||
| **Note:** The Fenwick tree presented here uses one-based indexing. |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Emphasize this is for didactic reasons, i.e. to make the indexing and ranges easier.
| Many people use a version of the Fenwick tree that uses one-based indexing. | ||
| As such, you will also find an alternative implementation which uses one-based indexing in the implementation section. | ||
| **Note:** The Fenwick tree presented here uses one-based indexing. | ||
| Many people use a version of the Fenwick tree that uses zero-based indexing. |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Most presentations I've seen are with one-based indexing.
| 1. First, it adds thesum of therange$[g(r), r]$ (i.e.$T[r]$) to the`result`. | ||
| 2. Then, it"jumps" to therange$[g(g(r)-1), g(r)-1]$and adds thisrange's sum to the `result`. | ||
| 3. This continues until it"jumps"from$[0, g(g( \dotsg(r)-1 \dots-1)-1)]$ to $[g(-1),-1]$; this is where the `sum` function stops jumping. | ||
| 1. First, it adds thesum of therange$(g(r), r]$ (i.e.$T[r]$) to the`result`. |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
result technically should beres
| 2. Then, it"jumps" to therange$[g(g(r)-1), g(r)-1]$and adds thisrange's sum to the `result`. | ||
| 3. This continues until it"jumps"from$[0, g(g( \dotsg(r)-1 \dots-1)-1)]$ to $[g(-1),-1]$; this is where the `sum` function stops jumping. | ||
| 1. First, it adds thesum of therange$(g(r), r]$ (i.e.$T[r]$) to the`result`. | ||
| 2. Then, it"jumps" to therange$(g(g(r)), g(r)]$and adds thisrange's sum to the `result`. |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
By applying g to the start and end indices
| 1. First, it adds thesum of therange$[g(r), r]$ (i.e.$T[r]$) to the`result`. | ||
| 2. Then, it"jumps" to therange$[g(g(r)-1), g(r)-1]$and adds thisrange's sum to the `result`. | ||
| 3. This continues until it"jumps"from$[0, g(g( \dotsg(r)-1 \dots-1)-1)]$ to $[g(-1),-1]$; this is where the `sum` function stops jumping. | ||
| 1. First, it adds thesum of therange$(g(r), r]$ (i.e.$T[r]$) to the`result`. |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Ther here is the initial value ofr. In the code it changes per loop.
| ### Finding sum in one-dimensional array | ||
| Here we present an implementation of the Fenwick treeforsum queriesand single updates. |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
You must state the API for the tree is 0-based as usual, even though internally it is 1-based. It is confusing
| It's possible to improve that to $O(N)$ time. | ||
| The ideais, that the number$a[i]$ at index$i$ will contribute to therange storedin$bit[i]$,and toall ranges that the index$i| (i+1)$ contributes to. | ||
| The ideais, that the number$a[i]$ at index$i$ will contribute to therange storedin$bit[i+1]$,and toall ranges that the index$i+ (i~\&~ (-i))$ contributes to. |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
unnecessary comma after "is"
| int n; | ||
| constintINF = (int)1e9; | ||
| FenwickTreeMin(int n) { |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
What does this code present then? Should we say segment tree can solve this problem for min ranges as min is associative?
| For this approach we change the requirementsand definitionfor$T[]$and$g()$ a little bit. | ||
| We want$T[i]$ to store thesum of$[g(i)+1; i]$. | ||
| We want$T[i]$ to store thesum of$[g(i); i]$. |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Is it possible to store [g(i), i) instead? This may be a separate PR.
| } | ||
| voidtest_fenwick_sum_onebased() { | ||
| usingnamespaceFenwick_Sum_Onebased; |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
The naming should be consistent. We have FenwickTree 1-based as the default, so the other one should be called 0-based.
| The lastset bit can be extracted using$i~\&~ (-i)$, so the operation can be expressed as: | ||
| $$h(j)=j~|~ (j+1),$$ | ||
| $$g(i)=i- (i~\&~ (-i)).$$ |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
This can also be implemented asr & (r-1), and that's what gcc will optimize it to.
Gcc didn't have any trick for the inverse operation h.
Issue reference:#1346
Solved the issues in my previous pull request and added 1-based approach as main approach throughout the article, also zero-based approach is still in a section for reference.
I tested this on some sample cases locally, feel free to test the codes again. Let me know if there are still any problems with this article. Thank you for accepting my pull request in advanced.