传递参数时抛出异常

Question

我遇到错误 Exception thrown at 0x009523B9 in Project5.exe: 0xC00000FD: Stack overflow (parameters: 0x00000001, 0x00E42ED4). 在下面的程序中

测试用例：

5

1 2 3 4 5

1

Q 2 4

执行这一行时出现错误 struct node query(int index, int start, int endv, int l, int r) 那是在 main

中第一次调用 query 函数的时候

异常抛出时的参数应该是 query(0,0,4,1,3)

但它们会自动更改为 query(0,1,1,1,3) 我哪里做错了

这是基于线段树的问题spoj KGSS

#include<iostream>
#include<algorithm>
#include<climits>
#pragma warning(disable:4996)    //disable scanf warning 
using namespace std;

struct node {
    long long int maxsum;
    long long int maxnum;
};
long long int a[100];
struct node tree[100];
void build(int index, int start, int endv) {
    if (start == endv) {
        tree[index].maxsum = a[start];
        tree[index].maxnum = a[start];
    }
    else {
        int mid = (start + endv) / 2;
        build(2 * index + 1, start, mid);
        build(2 * index + 2, mid + 1, endv);

        tree[index].maxnum = max(tree[2 * index + 1].maxnum, tree[2 * index + 2].maxnum);
        tree[index].maxsum = max(tree[2 * index + 1].maxnum + tree[2 * index + 2].maxnum, max(tree[2 * index + 1].maxsum, tree[2 * index + 2].maxsum));
    }
}

struct node query(int index, int start, int endv, int l, int r) {

    struct node result;

    result.maxnum = INT_MIN;
    result.maxsum = INT_MIN;

    if (l > endv || r < start)
        return result;
    int mid = (start + endv) / 2;
    struct node left, right;
    left = query(index, start, mid, l, r);
    right = query(index, mid + 1, endv, l, r);

    tree[index].maxnum = max(left.maxnum, right.maxnum);
    tree[index].maxsum = max(left.maxnum + right.maxnum, max(left.maxsum, right.maxsum));

    return tree[index];
}

void update(int index, int start, int endv, int aidx, long long int value) {


    if (start == endv) {
        a[aidx] = value;
        tree[index].maxsum = value;
        tree[index].maxnum = value;
    }
    else {

        int mid = (start + endv) / 2;
        if (aidx <= mid) {
            update(2 * index + 1, start, mid, aidx, value);
        }
        else {
            update(2 * index + 2, mid + 1, endv, aidx, value);
        }

        tree[index].maxnum = max(tree[2 * index + 1].maxnum, tree[2 * index + 2].maxnum);
        tree[index].maxsum = max(tree[2 * index + 1].maxnum + tree[2 * index + 2].maxnum, max(tree[2 * index + 1].maxsum, tree[2 * index + 2].maxsum));
    }
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    build(0, 0, n - 1);
    //for(int i = 0)
    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        int l, r;
        char ap;
        cin >> ap >> l >> r;
        if (ap == 'U') {
            update(0, 0, n - 1, l - 1, r);
        }
        else {
            struct node temp = query(0, 0, n - 1, l - 1, r - 1);
            printf("%lld\n", temp.maxsum);
        }
    }

}

注意 -> 我使用了 result.maxnum = INT_MIN; result.maxsum = INT_MIN;

在查询函数中 result.maxnum 和 result.maxsum 属于 long long int 类型，我正在为它们分配 INT_MIN。

这是因为有时从递归的两边我都得到最小值，然后添加这些值并将它们存储在 int 变量中会导致整数溢出，这就是为什么我使用 long long int 有人可以提供处理这种情况的方法还是可以的

Answer 1

    scanf("%d", &a[i]);

当 a[i] 的类型为 long long int 时，

不正确。将 C++ I/O 与 C I/o 混合使用也不是一个好主意。

没问题

cin >> a[i];

但主要问题是你有堆栈溢出。在你的例子中

query(0,0,4,1,3) ->
 query(0,0,2,1,3) ->
  query(0,0,1,1,3) ->
   query(0,0,0,1,3) ->
    return result
   query(0,1,1,1,3) ->
    query(0,1,1,1,3) ->
     query(0,1,1,1,3) ->
      query(0,1,1,1,3) ->
       query(0,1,1,1,3) ->
        query(0,1,1,1,3) ->
         query(0,1,1,1,3) ->
          BOOM!! stack overflow

不太确定如何修复它，因为我不理解代码。我会想到像

if (start >= endv)
    return result;

一开始会有帮助，但我不太确定。

传递参数时抛出异常

exception thrown while passing parameters

c++

segment-tree