Diksha_goyal's blog

Fenwick tree understanding
By Diksha_goyal, history, 5 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?
»
5 years ago, hide # |
← 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 \lt i$$$ and $$$A[j] \lt =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 \lt i\ and\ A[j] \lt =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
»
5 years ago, hide # |
← 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