Решая задачу 1042D - Petya and Array, столкнулся с приведенной в заголовке проблемой. В редакционной статье написано, что это можно реализовать используя дерево Фенвика или дерево отрезков. В просторах интернета реализацию Фенвика или дерева отрезков именно для этой задачи не нашел.