动态范围求和查询

Question

我正在解决 CSES 问题。这是一个简单的芬威克树问题，我编写了代码，该代码在较小的输入上完美运行，但在较大的输入上给出了错误的答案。 问题链接：https://cses.fi/problemset/task/1648/ 我的问题解决方案：

#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;
}

这非常简单。我可能做错了什么？

Answer 1

你问你做错了什么，所以我来了：

1. 您使用

   #include <bits/stdc++.h>

   ：为什么我不应该#include ？
2. 你使用

   using namespace std;

   ：为什么是“using namespace std;”被认为是不好的做法吗？
3. 您使用

   typedef long long ll;

   只会混淆您的代码。
4. 您使用全局变量和固定长度数组，根本不需要任何大小检查。
5. 您不要在任何运算符及其参数之间使用空格（这是一种偏好）。
6. 请永远不要使用小写 L 作为变量名。

关于代码失败的原因，可以通过调试这样的失败案例来找到答案：

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

查询 #1 需要 1 到 4 的和，正确给出 14。然后 Q#2 将元素号 3（4）更改为 1，因此 Q#3 给出 11，再次正确。现在 Q#4 将元素编号 3 设置为 100，因此从 1 到 4 的总和应为 110，但 Q#5 给出 107。

您现在应该调试并了解为什么会这样。或者您可以阅读以下原因：

为了更新 Fenwick 树，您需要删除以前的值并使用

add(k, p-a[k]);

添加新值。您假设先前的值在数组

a

中可用，但您忘记也更新它！只需在该行后面添加一个

a[k] = p;

即可。

另一种选择是

使用

add(k, p - sum(k) + sum(k - 1));

直接从 Fenwick 树中提取值。速度较慢，但不需要将原始数组保留在内存中（可以就地构建芬威克树），因此这在受限内存设置中是有意义的。但总的来说我更喜欢你的解决方案。

Answer 2

不要对 type == 2 使用 else，而是使用 if 语句 我不知道为什么还会失败。