1
問題陳述：範圍更新/查詢二進制索引樹
https://www.hackerrank.com/contests/epiccode/challenges/square-array
鑑於整數數組A1，A2，... AN，你必須在陣列中執行兩種類型的 查詢。
1 x y。向Ax添加1×2，向Ax + 1添加2×3，向Ax + 2添加3×4，向Ax35添加4×5至 ，依次類推，直到Ay。
2 x y。找到從 指數x到指數y模109 + 7的所有整數的總和，即find（Ax + Ax + 1 + ... + Ay）mod（109 + 7）。
可以假定最初的陣列中的所有值爲0
輸入格式：
第一行包含兩個空間分開的整數，N 和Q. N表示數組的大小，Q表示查詢的數量。
接下來的Q行中的每一行都將包含1 x y或2 x y的查詢。
限制條件：
1≤x≤y≤N1≤N≤2×10^51≤Q≤2×10^5
輸出格式對於形式2的xy打印的每個查詢要求的 的答案。
Sample Input
10 5
1 1 10
2 2 7
1 4 8
1 5 6
2 6 6
Output:
166
60
說明：
After the first query, the array is [2,6,12,20,30,42,56,72,90,110]. The answer for the second query is 6+12+20+30+42=166. After the third query, the array is [2,6,12,22,36,54,76,102,90,110]. After the fourth query, the array is [2,6,12,22,38,60,76,102,90,110]. The answer for the fifth query is 60.
一個提交的解決方案：
#include <bits/stdc++.h>
const int N = 2 * 100005;
const long long MOD = 1000000007;
const long long INV = 333333336;
using namespace std;
int n;
int nQuery;
struct BIT {
int bit[N];
BIT() {
memset(bit, 0, sizeof(bit));
}
void inc(int i, int v) {
for (; i < N; i += i & -i) {
bit[i] += v;
bit[i] %= MOD;
}
}
void incRange(int i, int j, int v) {
inc(i, v); inc(j + 1, MOD - v);
}
int get(int i) {
int res = 0;
for (; i > 0; i -= i & -i)
res = (res + bit[i]) % MOD;
return res;
}
} First, Second, Third, Const;
int sum(long long x, long long y) {
return ((x + y) % MOD + MOD) % MOD;
}
void update(long long l, long long r) {
Third.incRange(l, r, 1);
Second.incRange(l, r, MOD - sum(l - 1, sum(l - 2, l - 3)));
First.incRange(l, r, sum((l - 1) * (l - 2) % MOD, sum((l - 2) * (l - 3) % MOD, (l - 1) * (l - 3) % MOD)));
Const.incRange(l, r, sum(MOD - (l - 1) * (l - 2) % MOD * (l - 3) % MOD, MOD));
Const.incRange(r + 1, n, (r - l + 1) * (r - l + 2) % MOD * (r - l + 3) % MOD);
}
int getSum(long long x) {
return (x * x % MOD * x % MOD * Third.get(x) % MOD + x * x % MOD * Second.get(x) % MOD + x * First.get(x) % MOD + Const.get(x)) % MOD * INV % MOD;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
#ifdef _LAD_
freopen("square-array.txt", "r", stdin);
#endif // _LAD_
cin >> n >> nQuery;
int x, y, type;
while (nQuery--) {
cin >> type >> x >> y;
if (type == 1) {
update(x, y);
#ifdef _LAD_
for (int i = 1; i <= n; ++i)
cout << ((getSum(i) - getSum(i - 1) + MOD) % MOD) << ' ';
cout << endl;
#endif // _LAD_
}
else
cout << (getSum(y) - getSum(x - 1) + MOD) % MOD << '\n';
}
return 0;
}
需要一些幫助..plzz – Nakshatra