动态范围求和查询
Dynamic Range Sum Queries
我正在解决一个 CSES 问题。这是一个简单的芬威克树问题,我编写了代码,它在较小的输入上完美运行,但对于较大的输入给出了错误的答案。
问题 link: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;
}
这很简单。我可能做错了什么?
你问你哪里做错了,我来:
- 您使用
#include <bits/stdc++.h>
:
- 您使用
using namespace std;
:Why is "using namespace std;" considered bad practice?
- 您使用
typedef long long ll;
只会混淆您的代码。
- 您使用全局变量和定长数组,根本没有任何大小检查。
- 您不在任何运算符和它们的参数之间使用空格(这是一种偏好)。
- Please never ever use lowercase L as a variable name.
关于为什么你的代码失败,可以通过调试像这样的失败案例找到答案:
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 树中提取值。速度较慢但不需要将原始数组保留在内存中(可以就地构建 Fenwick 树),因此这在受限内存设置中是有意义的。但总的来说我更喜欢你的解决方案。
我正在解决一个 CSES 问题。这是一个简单的芬威克树问题,我编写了代码,它在较小的输入上完美运行,但对于较大的输入给出了错误的答案。 问题 link: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;
}
这很简单。我可能做错了什么?
你问你哪里做错了,我来:
- 您使用
#include <bits/stdc++.h>
: - 您使用
using namespace std;
:Why is "using namespace std;" considered bad practice? - 您使用
typedef long long ll;
只会混淆您的代码。 - 您使用全局变量和定长数组,根本没有任何大小检查。
- 您不在任何运算符和它们的参数之间使用空格(这是一种偏好)。
- Please never ever use lowercase L as a variable name.
关于为什么你的代码失败,可以通过调试像这样的失败案例找到答案:
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 树中提取值。速度较慢但不需要将原始数组保留在内存中(可以就地构建 Fenwick 树),因此这在受限内存设置中是有意义的。但总的来说我更喜欢你的解决方案。