c++ - 对二进制字符串进行范围查询？

Question

二进制-十进制
我们得到一个 二进制字符串 S of 长度 n , 其中每个字符是 “1”或“0” .
我们被要求对字符串执行几个查询。
在每个查询中，我们都会得到整数 大号 和 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] 转换为十进制。
我 预计算 的结果S[i...n-1] 为所有 i:[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;

以上接近仅限 sample 测试用例 通过了，所有其他情况都给出了错误答案(WA) .
我什至尝试使用 段树 对于这个问题，但这也不起作用。

What is the correct approach to solve this problem ?

Answer 1

定义 V[k]为 S 的数字的值从 k 开始第一个。
那么子串的值S[l..r] = (V[l] - V[r+1]) / 2^(n - r - 1) . (类似的东西，我可能有一个错误。玩一些小例子。)
现在关于 10^9 + 7 的有用事实是它是一个素数。 (前 10 位素数。)这意味着除以 2 与乘以 2^(10^9 + 5) 相同。 .这是一个常数，您可以通过重复平方来计算。使用重复平方可以非常有效地将该常数提高到高功率。
有了这个，您可以为 V 创建一个查找表。 ，然后及时查询O(log(n)) .