marblegef DOUBT..

chaseme · February 17, 2014, 4:33pm

i did this problem http://www.codechef.com/problems/MARBLEGF using segmented tree concept…but i am getting tle…editorial say to use fenwick tree concept…But i came to know both fenwick tree and segmented tree have same time complexity in worst case which is O(mlogn)…anyone clear my doubt plsss…thanks in advance:)

this is my code which uses the concept of segment tree http://www.codechef.com/viewsolution/3436231

dragonemperor · February 18, 2014, 8:40pm

I read somewhere that the constant factor in complexity calculation of segment tree is more than BIT. So for extremely steep time limit, BIT is effective.