設計の違い
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|"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]