##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
Complexity comparison
Compare approaches: Segment tree: per operation, total Sqrt decomposition: per query, per update For : segment tree does about operations, sqrt does about query operations plus update operations.
Both work here. Segment trees are faster asymptotically, but sqrt decomposition is simpler to implement. In contests, simpler often means fewer bugs.
