設計の違い

old

• 範囲に対して遅延された作用の適用を強制する
  • これは値テーブルと作用テーブルの両方を更新する操作
    • 値は作用が適用されて更新される
    • 作用は消えて、子に伝搬する python

>>> force_range_update(value_table, action_table, 0, 6, PowAction(1))
>>> debugprint(value_table, minsize=3)
|            abcdefgh           |
|    (abcd)^2   |      efgh     |
|   ab  |   cd  | (ef)^2|   gh  |
| a | b | c | d | e | f | g | h |

>>> debugprint(action_table)
|           ^1          |
|     ^1    |     ^1    |
|  ^2 |  ^2 |  ^1 |  ^1 |
|^1|^1|^1|^1|^2|^2|^1|^1|

- まず範囲の両端に関して遅延された作用を下に伝播する
    - これは作用テーブルだけに関する操作
    - 範囲に作用するときに、今の作用の値が必要だから、必要な分だけ下ろしている
    - これは双対セグメント木で、末端の値が必要になったときに下に伝搬するのと同じ

python

>>> down_propagate(action_table, up(1), lambda x, y: x(y), PowAction(1))
>>> down_propagate(action_table, up(5), lambda x, y: x(y), PowAction(1))
>>> debugprint(action_table)
|           ^1          |
|     ^1    |     ^1    |
|  ^1 |  ^2 |  ^1 |  ^1 |
|^2|^2|^1|^1|^2|^2|^1|^1|