Added 1-based indexing approach in fenwick tree #1376
Conversation
|
Btw you do not need to open a new PR. If you update your branch it will show in the PR. |
|
Sorry, I am new to open source and I understood my previous PR was full of mistakes so I reopened a new PR |
|
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 |
|
@jxu Could you please review my changes and test my code if it is fit to merge |
|
@adamant-pwn Can you please review my pull request |
|
@adamant-pwn Can you please review my request? |
|
Hi, this is a brief non-update. Yes, I will look into this, but it might take a bit more time. |
|
No problem |
|
Off-topic: we should mention the Fenwick tree was actually first proposed by Boris Ryabko in 1989. It was published in Russian in Soviet 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.
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.
Most presentations I've seen are with one-based indexing.
| 1. First, it adds the sum of the range $[g(r), r]$ (i.e. $T[r]$) to the `result`. | ||
| 2. Then, it "jumps" to the range $[g(g(r)-1), g(r)-1]$ and adds this range's sum to the `result`. | ||
| 3. This continues until it "jumps" from $[0, g(g( \dots g(r)-1 \dots -1)-1)]$ to $[g(-1), -1]$; this is where the `sum` function stops jumping. | ||
| 1. First, it adds the sum of the range $(g(r), r]$ (i.e. $T[r]$) to the `result`. |
There was a problem hiding this comment.
result technically should be res
| 2. Then, it "jumps" to the range $[g(g(r)-1), g(r)-1]$ and adds this range's sum to the `result`. | ||
| 3. This continues until it "jumps" from $[0, g(g( \dots g(r)-1 \dots -1)-1)]$ to $[g(-1), -1]$; this is where the `sum` function stops jumping. | ||
| 1. First, it adds the sum of the range $(g(r), r]$ (i.e. $T[r]$) to the `result`. | ||
| 2. Then, it "jumps" to the range $(g(g(r)), g(r)]$ and adds this range's sum to the `result`. |
There was a problem hiding this comment.
By applying g to the start and end indices
| 1. First, it adds the sum of the range $[g(r), r]$ (i.e. $T[r]$) to the `result`. | ||
| 2. Then, it "jumps" to the range $[g(g(r)-1), g(r)-1]$ and adds this range's sum to the `result`. | ||
| 3. This continues until it "jumps" from $[0, g(g( \dots g(r)-1 \dots -1)-1)]$ to $[g(-1), -1]$; this is where the `sum` function stops jumping. | ||
| 1. First, it adds the sum of the range $(g(r), r]$ (i.e. $T[r]$) to the `result`. |
There was a problem hiding this comment.
The r here is the initial value of r. In the code it changes per loop.
|
|
||
| <center></center> | ||
| As you can see, the main benefit of this approach is that the binary operations complement each other very nicely. | ||
|
|
||
| ## Implementation | ||
|
|
||
| ### Finding sum in one-dimensional array | ||
|
|
||
| Here we present an implementation of the Fenwick tree for sum queries and single updates. |
There was a problem hiding this comment.
You must state the API for the tree is 0-based as usual, even though internally it is 1-based. It is confusing
| @@ -181,22 +153,22 @@ struct FenwickTree { | |||
| The above implementation requires $O(N \log N)$ time. | |||
| It's possible to improve that to $O(N)$ time. | |||
|
|
|||
| The idea is, that the number $a[i]$ at index $i$ will contribute to the range stored in $bit[i]$, and to all ranges that the index $i | (i + 1)$ contributes to. | |||
| The idea is, that the number $a[i]$ at index $i$ will contribute to the range stored in $bit[i+1]$, and to all ranges that the index $i + (i ~\&~ (-i))$ contributes to. | |||
| @@ -208,23 +180,23 @@ struct FenwickTreeMin { | |||
|
|
|||
| FenwickTreeMin(int n) { | |||
There was a problem hiding this comment.
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 requirements and definition for $T[]$ and $g()$ a little bit. | ||
| We want $T[i]$ to store the sum of $[g(i)+1; i]$. | ||
| We want $T[i]$ to store the sum of $[g(i); i]$. |
There was a problem hiding this comment.
Is it possible to store [g(i), i) instead? This may be a separate PR.
| @@ -68,7 +68,7 @@ void test_fenwick_sum_onebased() { | |||
| using namespace Fenwick_Sum_Onebased; | |||
There was a problem hiding this comment.
The naming should be consistent. We have FenwickTree 1-based as the default, so the other one should be called 0-based.
|
|
||
| $$h(j) = j ~|~ (j+1),$$ | ||
| $$g(i) = i - (i ~\&~ (-i)).$$ |
There was a problem hiding this comment.
This can also be implemented as r & (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.