Решим следующую задачу: Требуется уметь находить произведение чисел на отрезке по модулю, а также умножать все числа на отрезке на некое число x на отрезке. И все по модулю

Понятно, что это решается обычным деревом отрезков с отложенными массовыми операциями. Но в этом случае мы при каждом вызове функции get и update будем пушить значения в детей, что очень долго (У нас в этом случае будет 4 умножения по модулю в функции push). Давайте научимся делать массовые операции не проталкивая значения в детей.

Утверждение, такой код работает (там есть беды с переполнением, но это остается, как упражнение читателю):

Функция update:

void update(int v, int l, int r, int L, int R, int val) {
    if (R <= l || r <= L)
        return;
    if (L <= l && r <= R) {
        t[v] = (t[v] * pow(val, (r - l))) % MOD;
        mod[v] = (mod[v] * val) % MOD;
        return;
    }

    int m = (l + r) / 2;
    update(v * 2 + 1, l, m, L, R, val);
    update(v * 2, m, r, L, R, val);
    t[v] = t[v * 2 + 1] * t[v * 2] * pow(mod[v], (r - l)) % MOD;
}

Функция get:

int get(int v, int l, int r, int L, int R) {
    if (R <= l || r <= L)
        return 1;
    if (L <= l && r <= R)
        return t[v];

    int m = (l + r) / 2;
    return get(v * 2 + 1, l, m, L, R) * get(v * 2, m, r, L, R) * pow(mod[v], max(L, l) - min(R, r)) % MOD;
}

Почему это так: понятно, что в вершине корректное значение, если мы не смотрим на обновления, которые были сверху. (По аналогии с обычным деревом отрезков). Ну а верхние обновления мы учтем, когда будем спускаться в функции get.

Брать модуль у числа не самое быстрое занятие, поэтому функция push в ДО работает очень долго, и такой способ написания ДО очень сильно ускоряет код (когда я пихал корнячку с таким ДО (ну и там не только операции с ДО были) время с 8 секунд уменьшилось до 6, что очень и очень существенно) Ну и это также работает с минимумом/максимумом/суммой и многими другими функциями, и работает быстрее. Такие вот пироги