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.
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$$$.
how BIT is helping getting the sum of all A[j]<=A[i] for j<i
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]$$$.
i'm not getting how sum is ensuring the value that A[i]>=A[j] and j<i
Maybe this tutorial on BIT can help clarify your doubts :)
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