二进制字符串的范围查询？

Question

二进制-十进制

我们得到一个长度为n的二进制字符串 S，其中每个字符要么是'1'或 '0'.

并且要求我们对字符串执行多个查询。

在每个查询中，我们得到整数 L 和 R。而我们要告诉子串S[l..r]的值，用十进制表示.

示例测试用例：

Input:

1011 (string S)
5    (number of queries)
1 1  (l, r)
2 2
1 2
2 4
1 4

Output:
1      (1 * 2^0 == 1)
0
2
3      (0 * 2^2 + 1 * 2^1 + 1 * 2^0)
11     (1 * 2^3 + 0 * 2^2 + 1 * 2^1 + 1 * 2^0 = 11)

约束

1 < N < 10^5
1 < Q < 10^5

由于数字可能很大，我们需要打印它模 10^9 + 7.

接近

所以基本上我们需要将二进制表示子字符串 S[l..r] 转换为十进制。

I 预先计算所有i的S[i...n-1]的结果: [0, n-1] 在 数组 B 中。所以现在B[i]表示子串S[i..n-1].

的十进制数表示

vector<int> pow(1e5, 1);
for(int i = 1; i < 1e5; i++) {
    pow[i] = (pow[i - 1] * 2) % mod;
}

string s;
getline(cin, s);
vector<int> B(n, 0);
int prev = 0;
for(int i = 0; i < n; i++) {
    B[(n - 1) - i] = (prev + (s[(n - 1) - i] == '1' ? pow[i] : 0)) % mod;
    prev = B[(n - 1) - i];
}

while(q--) {
    int l, r;
    cin >> l >> r;
    cout << ((B[l] - (r + 1 < n ? B[r + 1] : 0) + mod) % mod) / pow[n - (r + 1)]<< "\n";
}

return 0;

使用上述方法只有示例测试用例通过了，所有其他案例都给出了错误的答案（WA ).

我什至尝试使用 线段树 来解决这个问题，但这也不起作用。

What is the correct approach to solve this problem ?

Answer 1

定义V[k]为从第k位开始的S位的值

然后子串的值S[l..r] = (V[l] - V[r+1]) / 2^(n - r - 1)。（类似的东西，我可能有一个错误。玩小例子。）

现在关于 10^9 + 7 的有用事实是它是一个素数。（第一个 10 位素数。）这意味着除以 2 与乘以 2^(10^9 + 5) 相同。这是一个常数，您可以通过重复平方计算得出。使用重复平方可以非常有效地将该常数提高到高次幂。

有了这个，您可以为 V 创建一个查找 table，然后及时进行查询 O(log(n))。

Answer 2

这似乎与常规总和相同 range-queries，除了 (1) 我们需要存储部分总和 mod 10^9 + 7，(2) 在检索期间，我们需要“将总和的相关部分按其右侧部分的长度移动。在这种情况下“移位”意味着乘以 2^(length_of_suffix) mod 10^9 + 7。当然，对 mod 10^9 + 7 的部分求和。

但 btilly 的似乎简单得多:)

二进制字符串的范围查询？

Range queries on a binary string?

c++

algorithm

math

data-structures

modulus