+56
- 01
- 02
- 03
- 04
- 05
- 06
- 07
- 08
- 09
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
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
absolut 05.04.2015 11:18 # +5
36,525 дней?
inkanus-gray 06.04.2015 11:24 # +1
roman-kashitsyn 06.04.2015 11:27 # +1
> Вместо того, чтобы написать один if
Где здесь нужен if ?
Janycz 06.04.2015 12:00 # 0
roman-kashitsyn 06.04.2015 12:03 # 0
А твой InitSummator не за линейное?
Очевидно, ты делаешь статический RangeSumQuery, который быстрее <O(n), O(1)> не сделаешь.
bormand 06.04.2015 12:25 # 0
roman-kashitsyn 06.04.2015 12:28 # 0
kegdan 06.04.2015 12:31 # 0
roman-kashitsyn 06.04.2015 12:32 # +3
ъ ъ ъ ъ ъ ъ ъ ъ
Держи, мне не жалко
kegdan 06.04.2015 12:51 # −1
HIV 29.05.2020 14:01 # 0
roman-kashitsyn 06.04.2015 12:07 # +1
Понял, в GetSum, чтобы обрабатывать запрос на нулевой индекс.
Если массив частичных сумм сместить на один индекс, как у тебя примерно и сделано, то никаких ифов не надо.
sums[r + 1] - sums[l].
TarasB 06.04.2015 13:10 # +1
bormand 06.04.2015 16:30 # 0
Janycz 06.04.2015 16:41 # 0
bormand 06.04.2015 16:44 # 0
roman-kashitsyn 06.04.2015 16:48 # 0
constructor 06.04.2015 20:06 # +1
Чтоб воры в мапу не залезли?