Есть целочисленный массив, элементы которого имеют границу инкрементации после которых обращаются в ноль(например ..., 34, 35, 0, 1, 2 ...), и нужно считать сумму элементов между определенными позициями, выводить ее, после чего эти элементы инкрементировать, потом делать то же самое снова, но между возможно другими позициями. Соответственно, количество операций будет равно сумме всех промежутков суммирования умноженной на два + проверки элементов на переход границы, а это достаточно долго. Можно ли каким-то образом оптимизировать этот процесс с учетом цикличности процессов?
-
Для массива наперед задан модуль (та самая величина, после которой элемент обращается в 0?). Этот модуль задан один на весь массив? В процесс счета модуль меняется?– gbg2 июл 2016 в 14:56
-
@gbg Да, модуль известен заранее. Нет, он не меняется.– Ka_ktus2 июл 2016 в 14:58
-
новый range для вычислений пересекает старый? Закон распределения начальных данных по массиву есть?– gbg2 июл 2016 в 15:01
-
@gbg Не обязательно, но может пересекать, в этом и был вопрос оптимизации. Изначально массив заполнен случайными положительными целыми числами. Области подсчета заранее корректны, известны номера первых элементов в области и номера последних, за границы массива они не выходят– Ka_ktus2 июл 2016 в 15:05
-
пока кроме очевидного распараллеливания и того факта, что если модуль - степень двойки, то его легко считать, ускорений не вижу. Новый интервал становится известен после того, как первый интервал просчитан? Или все интервалы суммирования известны заранее?– gbg2 июл 2016 в 15:08
1 ответ
Задача явно олимпиадная ну да ладно.
Общая идея - дерево отрезков с ленивыми операциями и поддержанием баланса вершин. Для простоты зафиксируем значение в MOD. Это не сильно усложнит задачу но отлаживать станет проще.
Да, здесь много умножений на 2, можете заменять на x+x
x<<1
и так далее как вам нравится.
Главная ссылка- http://e-maxx.ru/algo/segment_tree
Структура элемента
struct Node{
long sum;
int CountV[MOD];
int pending;
}
Нам понадобится вспомогательные функции:
void AddMod(int CountV[MOD], int delt){ //выполняет сдвиг массива
int temp[MOD]; //(можно оптимальнее)
memcpy(temp,CountV,MOD*sizeof(int));
for (int i=0;i<MOD;i++)
CountV[(i + delt) % MOD] = temp[i];
}
void addV(int &x, int y){ //добавляет число по модулю
x+=y;
x%=MOD;
}
void relax(int U, int d){ //добавляет в вершине отложенно d
AddMod(U, d);
addV(Tree[U].pending, d);
Tree[U].sum = 0;
for (int i = 0;i<10;i++)
Tree[U].sum += i*Tree[U].CountV[i];
}
void forcePush(int U){ //"пропихивает" через вершину отложенное
relax(2*U,Tree[U].pending);
relax(2*U + 1,Tree[U].pending);
Tree[U].pending = 0;
Tree[U].sum = 0;
for (int i = 0;i<10;i++)
Tree[U].sum += i*(Tree[U].CountV[i] = Tree[2 * U].CountV[i] +
Tree[2 * U + 1].CountV[i]);
}
Дальше делаем стандартное дерево корень в 1!:
void add(int U, int L, int R, int l, int r, int val) { //l,r - нужный
if (L >= r || R <= l) return; //отрезок
l = max(l, L);
r = min(R, r);
if (L == l && R == r) {
relax(U,val);
return;
}
forcePush(U);
add(2 * U, L, (L + R) >> 1, l, r, val);
add(2 * U + 1, (L + R) >> 1, R, l, r, val);
forcePush(U);
}
long getSum(int U, int L, int R, int l, int r) {
if (L >= r || R <= l)
return 0;
l = max(l, L);
r = min(R, r);
if (L == l && R == r)
return Tree[U].sum;
forcePush(U);
long res = getSum(2 * U, L, (L + R) >> 1, l, r) +
getSum(2 * U + 1, (L + R) >> 1, R, l, r);
return res;
}
void init(int U, int L, int R){
if (L >= R) return;
if (L + 1 == R){
Tree[U].CountV[ INIT[L] ] = 1;
Tree[U].sum = INIT[L];
return;
}
init(2*U,L, (L + R) >> 1);
init(2*U+1,(L + R) >> 1,R);
for (int i = 0;i<10;i++)
Tree[U].sum += i*(Tree[U].CountV[i] = Tree[2 * U].CountV[i] +
Tree[2 * U + 1].CountV[i]);
}
Ещё раз идея - в вершине дерева есть значение сколько туда протолкнули до этого. Когда надо считать сумму мы просто вытягиваем эти значения, когда идём вниз то проталкиваем это значение. Дальше вроде всё просто, что такое дерево рекомендую прочитать полностью.
Вызовы - getSum(1,0,MaxN, left, rigth);
По просьбе подробнее.
В каждой вершине мы знаем кол-во элементов равных i
в её отрезке.
Представим что запрос на добавление будет ровно на отрезок, покрываемый вершиной. Тогда мы ставим метку в вершину что туда добавлено и всё. Если покрытие не полностью, то выбора нет, идём влево и вправо, делаем пока полностью не совпадёт. Если в вершине было что-то а нам идти вниз, то сразу пропихнём значение вниз (можно пропихнуть при сумме, разницы нет, просто отлаживать легче).
Теперь сумма. Если мы пришли в вершину которая содержит ровно нужны отрезок, то мы сумму в ней можем легко посчитать из массива. (сумма i*Count[i]
).
Если нет, то идём вниз и пропихиваем значение. Теперь когда мы дошли до такой вершины нам нужно выполнить отложенное суммирование. Для этого достаточно вызвать функцию AddMod
описанную выше. Думаю объяснять не надо что она делает.
Код в полной сборке http://ideone.com/1vuNAm.
Тут можно оптимизировать (например 2 вызова forcePush(U);
в add
не нужны). Но это оставлю как упражнение :)
-
Спасибо! А могли бы вы объяснить, если не сложно, возможна ли реализация "цикличного" инкрементирования на дереве отрезков, реализация которого представлена по приведенной вам ссылке? (та реализация, если честно, просто намного понятнее, чем ваша. Или мне лучше разобраться в вашем коде?)– Ka_ktus2 июл 2016 в 18:36
-
@Ka_ktus та реализация базовая. Я поверх неё сделал цикличность сумм. Так что сначала дерево по ссылке, потом мой код. Если найду, я когда-то писал свой код на похожую задачу.– pavel2 июл 2016 в 18:48
-
А можете словесно описать (хоть примерно), как работает цикличность сумм в данном коде ?– Ka_ktus3 июл 2016 в 10:53
-
@Ka_ktus добавил. Но лучше вы сначала обычное дерево напишите, потом думаю понятнее станет.– pavel3 июл 2016 в 11:06
-
Хорошо. еще один вопрос: если я все правильно понял, то функция
add(...)
строит дерево отрезков. Если это так, то на основе чего она это делает? Нужен же вроде изначальный массив. Если нет, то зачем она, ведь она больше нигде не используется? И можете еще объяснить, чем является переменная pending? С остальным вроде бы все понятно– Ka_ktus3 июл 2016 в 11:45