帮我看下这个线段树代码哪里有问题

Question

帮我看下这个线段树代码哪里有问题:

代码:

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

        }
    }
}

Answer 1

让阿豪来帮你解答，本回答参考chatgpt3.5编写提供，如果还有疑问可以评论或留言

问题：这个线段树代码有哪些问题？

1. buildtree 函数中没有判断右儿子是否越界，应该改为 buildtree(k2, l, m); buildtree(k2+1, m+1, r)。
2. add 函数中的 f[k]+=y; 应该改为 f[k]+=y;。
3. calc 函数中少了一个括号，应该改为 t <= m。
4. 代码中没有输入数据的操作，应该先输入 n 和 m，再输入 a 数组的值。 修改后的代码如下：

#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, m) + calc(k * 2 + 1, m + 1, r, m + 1, 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) << endl;
        }
    }
    return 0;
}