Dynamic Range Sum Queries

Question

I was solving a CSES problem. It's a simple, Fenwick tree problem, and I write the code, which works perfectly on smaller inputs but giving wrong answers for larger inputs. the problem link: https://cses.fi/problemset/task/1648/ my solution to the problem:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int NMAX = 200005;
int n, q;
ll a[NMAX], tree[NMAX];


ll sum(int k){
    ll s = 0;
    while(k>0){
        s+=tree[k];
        k-=k&-k;
    }
    return s;
}

void add(int k, ll x){
    while(k<=n){
        tree[k]+=x;
        k+=k&-k;
    }
}



int main(){
    cin>>n>>q;
    for(int i = 1; i<=n; i++){
        cin>>a[i];
        add(i, a[i]);
    }
    while(q--){
        int type; cin>>type;
        if(type==1){
            int k; 
            ll p;
            cin>>k>>p;
            add(k, p-a[k]);
            a[k] = p;

        }
        else{
            int l, r; cin>>l>>r;
            cout<<sum(r)-sum(l-1)<<'\n';
        }
    }
    return 0;
}

which is pretty straightforward. what possibly I'm doing wrong?

Answer 1

You ask what you are doing wrong, so here I go:

1. You use #include <bits/stdc++.h>: Why should I not #include <bits/stdc++.h>?
2. You use using namespace std;: Why is "using namespace std;" considered bad practice?
3. You use typedef long long ll; which just obfuscates your code.
4. You use global variables and fixed length arrays without any size check at all.
5. You do not use spaces between any of your operators and their arguments (this is a metter of preference).
6. Please never ever use lowercase L as a variable name.

On why your code fails, the answer can be found by debugging a failure case like this one:

8 5
3 2 4 5 1 1 5 3
2 1 4
1 3 1
2 1 4
1 3 100
2 1 4

Query #1 requires the sum from 1 to 4 which correctly gives 14. Then Q#2 changes element number 3 (the 4) into a 1 so Q#3 gives 11, again correctly. Now Q#4 sets element number 3 to 100, so the sum from 1 to 4 should give 110, but Q#5 gives 107.

You should now debug and get why it is so. Or you can read the reason below:

In order to update the Fenwick tree you remove the previous value and add the new one with add(k, p-a[k]);. You assume that the previous value is available in array a, but you forget to also update it! Just add a a[k] = p; after that line.

Another option would be to

extract the value directly from the Fenwick tree with add(k, p - sum(k) + sum(k - 1));. Slower but without the need to keep the original array in memory (the Fenwick tree can be constructed in place), so this would make sense in constrained memory settings. But I prefer your solution in general.