Нашли или выдавили из себя код, который нельзя назвать нормальным, на который без улыбки не взглянешь? Не торопитесь его удалять или рефакторить, — запостите его на говнокод.ру, посмеёмся вместе!
+56
std::map<int, int> aSummator; //Массив частичных сумм
std::vector<int> v; //Исходный массив
void InitSummator()
{
aSummator[0] = v[0];
aSummator[-1] = 0;
for(int i = 1; i < int(v.size()); i++)
{
aSummator[i] = aSummator[i - 1] + v[i];
}
}
int GetSum(int l, int r)
{
return aSummator[r] - aSummator[l - 1];
}Как я писал сумматор 0.1 года назад. Вместо того, чтобы написать один if, я использовал std::map, что увеличило ассимптотику алгоритма на запрос с O(1) до O(log(n)). Но задачу при тех ограничениях (в массиве до 100000 элементов, запросов не более 100000) алгоритм решил. Преподу, естественно, показывать забоялся.
Запостил: 
Janycz,
03 Апреля 2015
Follow us!
36,525 дней?
> Вместо того, чтобы написать один if
Где здесь нужен if ?
А твой InitSummator не за линейное?
Очевидно, ты делаешь статический RangeSumQuery, который быстрее <O(n), O(1)> не сделаешь.
ъ ъ ъ ъ ъ ъ ъ ъ
Держи, мне не жалко
Понял, в GetSum, чтобы обрабатывать запрос на нулевой индекс.
Если массив частичных сумм сместить на один индекс, как у тебя примерно и сделано, то никаких ифов не надо.
sums[r + 1] - sums[l].
Чтоб воры в мапу не залезли?