计算一个字符串中一个字符在多次查询中出现的次数？

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

我们将保留每个字符在每个位置出现的次数，例如字符串abacaba

    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

现在，如果我们想要回答一个查询，我们执行以下操作

字母'a‘在3-5范围内

我们在位置5减去位置3之前的出现次数，即a5-a3-1=3-1=2在3到5的范围内有2个字母'a‘出现

Answer 2

搜索每个查询的范围的时间复杂度为O(n*q)

n:字符串长度

问: no.of查询

但是有一种更好的方法，你可以使用segment trees。

树构造的时间复杂度为O(N)，每次查询的时间复杂度为O(log(n))

因此，对于q个查询，时间复杂度将为O(q*log(n))