Alternate Fenwick Tree Implementation

question link - https://www.codechef.com/ENC2020/problems/ECFBP204
solution link - https://www.codechef.com/viewsolution/29839800
Can’t understand this code, can anyone explain. Is this idea common because two users has implemented this idea…
@ tmwilliamlin
Thanks.

I think it’s bottom up segment tree and not fenwick tree.

https://codeforces.com/blog/entry/18051

1 Like

Thanks, before this i never see this type of implementation.

1 Like

I would suggest you the classical implementation. I have tried this implementation (in real Contests) and trust me it doesn’t works at times for some unknown reasons, also if you want to add lazy propagation, this implementation would be a pain in a$$ while it’s just 4-5 new lines the other way

2 Likes

Lazy propogation in Fenwick tree??

1 Like

It’s not Fenwick Tree, it’s just segment tree written iteratively

Oh I didn’t see the above codes just saw replies , became curious to how lazy propogation works in Fenwick

Lazy propagation in fenwick tree:
https://codeforces.com/blog/entry/10306

2 Likes

Ohh, I didn’t knew range updates are nothing but lazy propogation I just used the normal method of how we did range updates over an array.
Thanks

1 Like