Diksha_goyal's blog

Fenwick tree understanding
By Diksha_goyal, history, 3 years ago, In English

I'm having a hard time understanding the editorial: https://atcoder.jp/contests/abc221/editorial/2732

for the problem: https://atcoder.jp/contests/abc221/tasks/abc221_e

I want to know how fen-wick tree is actually working in this problem. specially this block

for(int i=0; i<N; i++){
        ans += bit.sum(A[i])*modpow(2,i);
        ans %= mod;
        bit.add(A[i],modpow(div,i+1));
    }

I'm actually very new to CP and have no peers to seek help. So, I directly ask my problem through the blogs. please help me if you have an explanation to get me through it. Thanking you.

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

Comments Comments (6)
| Write comment?
»
3 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

For each $$$A[i]$$$ you need to find sum of all $$$2^{i-j}$$$ for $$$j<i$$$ and $$$A[j]<=A[i]$$$, so in the Fenwick tree we add $$$2^{-i}=modpow(div,i)$$$ to the position $$$A[i]$$$ and we get the all the sums of all $$$j<i\ and\ A[j]<=A[i]$$$ by querying $$$bit.sum(A[i])$$$ but since we need sum of all $$$2^{i-j}$$$ so we mutiply by $$$2^i$$$.

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

    how BIT is helping getting the sum of all A[j]<=A[i] for j<i

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

      You are moving in the array from left to right and storing sums at position at $$$A[i]$$$ so the $$$bit.sum(A[i])$$$ returns the sum from $$$1\ to\ A[i]$$$.

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

I had also learnt Fenwick Tree / BIT recently. Here is the video that helped me a lot :)
https://www.youtube.com/watch?v=RgITNht_f4Q

→ Reply