Дерево сегментов Java с ленивым распространением превышает лимит времени в CSES *Обновления диапазона и суммы* ⇐ JAVA

[Anonymous]

Я решаю проблему CSES:

https://cses.fi/problemset/task/1735/
Я реализовал дерево сегментов с отложенным распространением для поддержки:

• обновления приращения диапазона
• обновления назначения диапазона
• Запросы суммы диапазона

Ожидаемая сложность равна O((n + q) log n).
Однако мое решение получает TLE для больших входных данных (n, q ≤ 2e5).
Реализация проходит небольшие тесты, но превышает ограничение по времени для больших входных данных.
Вот упрощенная версия моего реализация:

Код: Выделить всё

static class Node {
boolean isSet;
long sum, increment, set;
}

Node[] segTree;

void push(int idx, int l, int r) {
if (segTree[idx].isSet) {
segTree[idx].sum = (r - l + 1) * segTree[idx].set;
if (l != r) {
segTree[2*idx].isSet = true;
segTree[2*idx].set = segTree[idx].set;
segTree[2*idx].increment = 0;

segTree[2*idx+1].isSet = true;
segTree[2*idx+1].set = segTree[idx].set;
segTree[2*idx+1].increment = 0;
}
segTree[idx].isSet = false;
}

if (segTree[idx].increment != 0) {
segTree[idx].sum += (r - l + 1) * segTree[idx].increment;
if (l != r) {
segTree[2*idx].increment += segTree[idx].increment;
segTree[2*idx+1].increment += segTree[idx].increment;
}
segTree[idx].increment = 0;
}
}

Я думаю, что возможными причинами могут быть:

• накладные расходы на объекты в Java
• неэффективная обработка отложенного распространения

Существуют ли известные оптимизации для этой проблемы в Java?>

Подробнее: https://stackoverflow.com/questions/799 ... n-cses-ran