I am trying to solve this problem: https://cses.fi/problemset/task/1648/ using Binary Indexed Tree. My solution does not work, but I think it is correct.
Heres is my code:
#include <bits/stdc++.h>
using namespace std;
const long MAXN = 2e5+5;
long n, q, arr[MAXN];
long long bit[MAXN];
void update(long x, long y) {
for (; x <= n; x += x&-x) bit[x] += y;
}
long long query(long x) {
long long sum = 0;
for (; x > 0; x -= x&-x) sum += bit[x];
return sum;
}
long long sum(long l, long r) { return query(r) - query(l-1); }
int main() {
ios::sync_with_stdio(false); cin.tie(0);
cin >> n >> q;
for (long i = 1; i <= n; i++) {
cin >> arr[i];
update(i, arr[i]);
}
while (q--) {
long i, a, b;
cin >> i >> a >> b;
if (i == 1) update(a, b-bit[a]);
else cout << sum(a, b) << "\n";
}
return 0;
}
Thanks for your time!!!
You should know when using a BIT, that it doesn't store the answer for an index directly. So,
update(a, b-bit[a])
is incorrect.You should keep track of the real values at each index, either by making another array, or calling $$$query(a)$$$ instead of using $$$bit[a]$$$.
Also, don't put your code directly, either upload it to some pastebin online and put the link here, or use spoiler provided by codeforces editor. People will be reluctant to help you if they see a long code at first glance.
Thanks for the help!!
I did this:
update(a, b-query(a))
and it is again wrong.b-(query(a)-query(a-1))
That would only work if you also update
arr[a]
which he doesn't. But again it's only one extra LOC.