Алгебра пометок

Прибавления складываются: две пометки $d_1$ и $d_2$ дают $d_1 + d_2$, порядок неважен. С присвоением так не выйдет.

Присвоение

Присвоение стирает всё, что было под ним, — и накопленные прибавления, и предыдущие присвоения.

void apply(int v, int tl, int tr, long long x) {
    sum[v] = x * (tr - tl + 1);
    assigned[v] = true;
    value[v] = x;
}

Флаг assigned обязателен отдельно от значения: присвоить можно и ноль, и по value[v] == 0 отличить «присвоено ноль» от «пометки нет» невозможно.

Схема «добавлять по дороге» здесь не работает: пометка предка обесценивает всё, что лежит ниже. Нужен честный push в начале и изменения, и запроса.

Когда операций две

Если в задаче есть и присвоение, и прибавление, пометка становится парой $(\text{assign}, \text{add})$ с фиксированным порядком применения:

$$\text{сначала присвоить } x, \text{ потом прибавить } d.$$

Присвоение может отсутствовать — тогда преобразование это просто «прибавить $d$».

Композиция:

• приходит прибавление $e$: было «присвоить $x$, прибавить $d$», стало «присвоить $x$, прибавить $d + e$»; присвоение не трогаем;
• приходит присвоение $y$: оно стирает всё, новая пометка — $(y, 0)$.

Обе строчки короткие, и обе легко написать неправильно. Проверка: примените к узлу присвоение, потом прибавление, потом снова присвоение — должно остаться только последнее присвоение.

void applyAssign(int v, int len, long long x) {
    sum[v] = x * len;
    hasAssign[v] = true; assignVal[v] = x; addVal[v] = 0;
}

void applyAdd(int v, int len, long long d) {
    sum[v] += d * len;
    addVal[v] += d;
}

В push порядок обязателен: сначала протолкнуть присвоение, потом прибавление. Наоборот — и прибавление, накопленное после присвоения, будет стёрто.

Как думать про пометки вообще

Пометка — это функция, применяемая ко всему отрезку. Композиция пометок — композиция функций, и вопрос «складываются ли пометки» — это вопрос «замкнут ли ваш класс функций относительно композиции».

Прибавления образуют группу сдвигов: $x \mapsto x + d$. Присвоения с прибавлениями — класс аффинных функций вида $x \mapsto \text{const}$ и $x \mapsto x + d$, и он тоже замкнут.

А вот «прибавить, но не больше чем до $c$» — уже нет: композиция двух таких операций не выражается третьей того же вида. Такие задачи решаются иначе — например, деревом с амортизацией (Ji Driver segment tree).

Практический вывод: прежде чем писать пометку, проверьте, что две ваши пометки складываются в одну того же вида. Если не складываются, дерево в лоб не поможет.