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

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

输出将是：

类似的问题是找出一个字符在字符串中出现的次数，但复杂度为 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

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

3-5 范围内的字母 'a'

我们在位置5减去位置3之前的出现次数做a，即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)，每个查询的时间复杂度为 O(log(n))

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

Count the number of occurrences of a character in a string for a number of queries?