SPOJ D-Query, BIT, но как?

Я пытаюсь решить проблему D-запроса на Spoj. http://www.spoj.com/problems/DQUERY/ Я думаю об установке и запоминании результата, но это действительно медленно. Так что я думал о том, что дерево с двоичными индексами может помочь мне получить lgN за один запрос, но я не могу придумать решение с этим. Может кто-нибудь мне помочь.