AC with RB tree(.046 sec 125kb). possible to solve with
TREAP:BST too.

Please somebody explain me the BIT method.

For the BIT method you just have to think about the right order to add the stars.