Fenwick tree understanding

Revision en2, by Diksha_goyal, 2021-10-06 17:08:27

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.

Tags fenwick tree, problem searching, algorithm complexity, dynamic programming, atcoder, difficult, help

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English Diksha_goyal 2021-10-06 17:08:27 178
en1 English Diksha_goyal 2021-10-06 16:31:22 463 Initial revision (published)