文字列内の文字のうち、いくつかのクエリの出現回数をカウントしますか？

Question

私は、n個のクエリ文字列内の文字の出現を見つけたい：例えば 文字列は次のとおりです。「i_love_mathematics」 とタスクが発生見つけることです。「i」は範囲で

を：

  1-4(a substring starting from 1st character and ending at 4th) 
      2-5 
      3-10 

'_' の範囲内：

  1-10 
      3-9 

出力は次のようになります。

  1 
      0 
      0 
      2 
      1 

同様の質問は、文字列内の文字の出現回数を調べることでしたが、その複雑さはO（N）でしたが、この場合、非常に複雑になるでしょう。この問題を解決するために使用できるデータ構造我々は、次の

の手紙「を実行クエリに答えるためにしたい場合は

Answer 1

私たちは、今

a b a c a b a 
| |1|2|3|4|5|6|7 
a | 1 1 2 2 3 3 4 
b | 0 1 1 1 1 2 2 
c | 0 0 0 1 1 1 1 

abacaba例えば、各位置で文字列を各文字の出現回数を保持します'範囲内3-5

位置5から位置3の前、つまりa [5] -a [3-1] = 3-1 = 2の位置で、2回の文字が出現する'a'は3〜5の範囲にあります。

Answer 2

一人ひとりクエリはO（N * Q）になるために範囲を検索するための

時間の複雑さは

N：文字列

Qの長さ：は、No.ofは

を照会しかし、より良い方法がありますそれを行うには segment treesを使用できます。ツリー構築のため

時間計算量はO（N）であり、Qは、時間複雑性はO（Q *ログ（N））

あろうクエリのクエリごとに、O（）N（ログ）

だからであります