ZeyadKhattab's blog

Doubt about Fenwick Tree
By ZeyadKhattab, history, 6 years ago, In English

It is commonly known that we can use Fenwick Tree to perform 2 tasks :

1) calculate the prefix sum (a[1]+a[2]+...+a[idx-1]+a[idx]) up to some index

2) increment a certain index by a certain value

but, my question is how can we modify the fenwick tree implementation so that instead of calculating prefix sums, we are calculating suffix sums so the sum we are now querying is (a[idx]+a[idx+1]+...+a[n-1]+a[n]), so I tried to change the implementation by basically swapping the indices that are accessed in the update and the query functions and I tried submitting in different problems and the submissions are accepted and I wanted to know if someone had a proof of why does it work ?

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
6 years ago, # |
← Rev. 2   Vote: I like it +9 Vote: I do not like it

Here's an intuition: think of which suffix sums are affected when an index is updated. And which sums are obtained when querying the tree.

anyway, you could have used inclusion-exclusion instead of modifying the tree.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes, I understand that I can use inclusion exclusion, but I am still curious to know about how to edit the tree, and I tried to think about what you said, but I was not able to understand why it works yet

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Fenwick Tree implementation relies on a math operator P = P&-P. Reversing the tree to get the suffix is hard because of that operator. The easy way to get suffix implementation is to swap values as you mentioned i = N-i. But for some reason, Inclusion and Exclusion was faster anyway.

      If you want to do suffix Fenwick tree, you can also use the sum of the whole array S and get the suffix sum as S-Prefix(P) and edit S wen you edit the Tree, but again Inclusion and Exclusion was faster for some reason.

      → Reply