Alternate Fenwick Tree Implementation

help
1

question link - CodeChef: Practical coding for everyone
solution link - CodeChef: Practical coding for everyone
Can’t understand this code, can anyone explain. Is this idea common because two users has implemented this idea…
@ tmwilliamlin
Thanks.

2

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

1 Like
3

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

1 Like
4

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
5

Lazy propogation in Fenwick tree??

1 Like
6

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

7

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

8

Lazy propagation in fenwick tree:

2 Likes
9

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