1

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 gives 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 am I possibly doing wrong?

Improve this question

2 Answers 2

Reset to default
5

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

@anandsingh I added another option, if you're interested.
0

Instead of using else for type == 2 use an if statement I do not know why else fails.

Improve this answer

3 Comments

"I do not know why else fails" How do you know that else fails?
This does not provide an answer to the question. Once you have sufficient reputation you will be able to comment on any post; instead, provide answers that don't require clarification from the asker. - From Review
Because i have also solved that question on cses with fenwick trees .... Also to why else fails it could be possibly due to large numbers and coz of server may be but if you use else and then run your code in your system then the output you get will be exactly same as that of cses output.txt i have matched it so else doesn't actually fails if could be something related to site only my solution link i was also failing when get WA verdict when i eas using else cses.fi/paste/3e16621924d220a9ad7f79.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.