与えられたデータの文字列についてTrie木を構築します
そのTrie木をEuler-TourしてBITを構築します
Trie木の頂点ごとに、BITで対応する範囲[l, r]がどこなのかも一緒に計算しておきます
その後、文字列ごとに、もう一度Trie木を潜ってその文字列の最後の頂点がBITのどこに対応するかを計算します
クエリ1は、その文字列の最後の頂点に対応するBITの値を+xする
クエリ2は、その文字列の最後の頂点に対応するBITの範囲のsumを取る(対応する頂点がない場合は0)
おまけ
クエリ3として、文字列Sが与えられるから
全部のデータについて(Sとの共通しているprefixの長さ)*値 の sum を求める
というクエリが追加される
例えば
{kitayuta, 100}
{kitakita, 10}
{kitsune, 30}
{kansai, -10}
にS=kitaが与えられたら
(4 * 100)(kita) + (4 * 10)(kita) + (3 * 30)(kit) + (-10 * 1)(k) = 520
となる
クエリ3で与えられる文字列の長さも総和は10^6以下
