帮我看下这个线段树代码哪里有问题:
代码:
#include "iostream"
using namespace std;
int n, m, a[500005], f[2000005]; //f:树要有4*n个结点(代表每个的区间),a:读进去的数据
void buildtree(int k, int l, int r) { //当前这个点的标号为k,左端点l,右端点r(k对应的区间是[l,r])
if (l == r)
{
f[k] = a[l]; //先把a数组里对应数字的值给求出来
return;
}
int m = (l + r) / 2;
buildtree(k * 2, l, m); //左树
buildtree(k * 2 + 1, m + 1, r); //右树
f[k] = f[k * 2] + f[k * 2 + 1]; //依次把数字累加到区间
}
void add(int k, int l, int r, int x, int y) { //把第x个值加上y
f[k] += y;
if (l == r)
return;
int m = (l + r) / 2;
if (x <= m)
add(k * 2, l, m, x, y);
else add(k * 2 + 1, m + 1, r, x, y);
}
int calc(int k, int l, int r, int s, int t) { //输出[s,t]的累加值
if (l == s && r == t) //当区间一样时直接输出区间值
return f[k];
//不然就做下面的
int m = (l + r) / 2;
if (t <= m) //如果区间全在左区间
{
return calc(k * 2, l, m, s, t);
}
else if (s > m) //如果区间全在右区间
{
return calc(k * 2 + 1, m + 1, r, s, t);
}
else return calc(k * 2, l, m, s, t) + calc(k * 2 + 1, m + 1, r, s, t); //不然就是在两个区间里,所以就加起来
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> a[i];
buildtree(1, 1, n); //建树,一开始是标号为1的点对应的1-n的区间
for (int i = 1; i <= m; i++) {
int t, x, y;
cin >> t >> x >> y;
if (t == 1) //给第x个数加上y
{
add(1, 1, n, x, y);
}
else { //不然输出[x,y]这个区间的和
cout << calc(1, 1, n, x, y);
}
}
}