0

Есть целочисленный массив, элементы которого имеют границу инкрементации после которых обращаются в ноль(например ..., 34, 35, 0, 1, 2 ...), и нужно считать сумму элементов между определенными позициями, выводить ее, после чего эти элементы инкрементировать, потом делать то же самое снова, но между возможно другими позициями. Соответственно, количество операций будет равно сумме всех промежутков суммирования умноженной на два + проверки элементов на переход границы, а это достаточно долго. Можно ли каким-то образом оптимизировать этот процесс с учетом цикличности процессов?

11
  • Для массива наперед задан модуль (та самая величина, после которой элемент обращается в 0?). Этот модуль задан один на весь массив? В процесс счета модуль меняется?
    – gbg
    2 июл 2016 в 14:56
  • @gbg Да, модуль известен заранее. Нет, он не меняется.
    – Ka_ktus
    2 июл 2016 в 14:58
  • новый range для вычислений пересекает старый? Закон распределения начальных данных по массиву есть?
    – gbg
    2 июл 2016 в 15:01
  • @gbg Не обязательно, но может пересекать, в этом и был вопрос оптимизации. Изначально массив заполнен случайными положительными целыми числами. Области подсчета заранее корректны, известны номера первых элементов в области и номера последних, за границы массива они не выходят
    – Ka_ktus
    2 июл 2016 в 15:05
  • пока кроме очевидного распараллеливания и того факта, что если модуль - степень двойки, то его легко считать, ускорений не вижу. Новый интервал становится известен после того, как первый интервал просчитан? Или все интервалы суммирования известны заранее?
    – gbg
    2 июл 2016 в 15:08

1 ответ 1

3

Задача явно олимпиадная ну да ладно.

Общая идея - дерево отрезков с ленивыми операциями и поддержанием баланса вершин. Для простоты зафиксируем значение в 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 не нужны). Но это оставлю как упражнение :)

14
  • Спасибо! А могли бы вы объяснить, если не сложно, возможна ли реализация "цикличного" инкрементирования на дереве отрезков, реализация которого представлена по приведенной вам ссылке? (та реализация, если честно, просто намного понятнее, чем ваша. Или мне лучше разобраться в вашем коде?)
    – Ka_ktus
    2 июл 2016 в 18:36
  • @Ka_ktus та реализация базовая. Я поверх неё сделал цикличность сумм. Так что сначала дерево по ссылке, потом мой код. Если найду, я когда-то писал свой код на похожую задачу.
    – pavel
    2 июл 2016 в 18:48
  • А можете словесно описать (хоть примерно), как работает цикличность сумм в данном коде ?
    – Ka_ktus
    3 июл 2016 в 10:53
  • @Ka_ktus добавил. Но лучше вы сначала обычное дерево напишите, потом думаю понятнее станет.
    – pavel
    3 июл 2016 в 11:06
  • Хорошо. еще один вопрос: если я все правильно понял, то функция add(...) строит дерево отрезков. Если это так, то на основе чего она это делает? Нужен же вроде изначальный массив. Если нет, то зачем она, ведь она больше нигде не используется? И можете еще объяснить, чем является переменная pending? С остальным вроде бы все понятно
    – Ka_ktus
    3 июл 2016 в 11:45

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.