求解区间加后数组最大值的两段C++代码为何一段正确一段段错误

给定一个长度为n、初始值全为0的1索引数组，你需要执行m次如下操作：
每次操作给出3个整数a、b、k，将数组下标从a到b（包含两端）的所有元素值加上k。所有操作执行完成后，返回数组中的最大值。

输入格式 #

第一行包含两个空格分隔的整数n和m，分别为数组长度和操作次数。
接下来m行，每行包含三个空格分隔的整数a、b、k，分别为区间左索引、区间右索引和待加的整数值。

约束条件 #

1 <= n, m <= 10^5
1 <= a <= b <= n
-10^9 <= k <= 10^9

示例 #

示例输入1：

10 3
1 5 3
4 8 7
6 9 1

示例输出1：

10

解释：n=10，m=3，三次操作执行完成后数组最大值为10。

示例输入2：

5 3
1 2 100
2 5 100
3 4 100

示例输出2：

200

解释：三次操作执行完成后数组最大值为200。

可正常运行的代码 #

#include <iostream>
#include <vector>
using namespace std;

int main() {
  int n, m;
  cin >> n >> m;

  vector<long long int> arr(n, 0);

  for (int i = 0; i < m; i++) {
    int start, finish, value;
    cin >> start >> finish >> value;
    arr[start - 1] += value;
    arr[finish] -= value;
  }

  long long int ans = 0;
  long long int current = 0;

  for (int value : arr) {
    current += value;
    if (current > ans) {
      ans = current;
    }
  }

  cout << ans;

  return 0;
}

触发段错误的代码 #

#include <bits/stdc++.h>

using namespace std;

int main(){
    long long int n,m;
    cin>>n>>m;
    long long int x[n] ={0};
    for(int i=0;i<m;i++)
    {
        long long int a,b,k;
        cin>>a>>b>>k;
        x[a-1] += k;
        if(b<n)
           x[b] -= k;
    }
    long long int max=0,current=0;
    for(int i=0;i<n;i++)
    {
        current=x[i]+current;
        if(max<current)
            max=current;
    }
    cout<<max<< endl;
    return 0;
}

两段代码的核心差异 #

• 内存分配方式不同：第一段使用C++标准库的vector容器分配数组内存，属于堆内存分配；第二段使用变长数组（VLA）分配内存，属于栈内存分配。
• 语法合规性不同：vector是C标准支持的特性，兼容性强；变长数组不是C标准规定的语法，仅为GCC等编译器的扩展实现，兼容性差。
• 初始化方式不同：vector支持传入长度参数直接将所有元素初始化为0；变长数组不支持={0}的批量初始化语法。
• 边界处理略有不同：第一段未判断finish < n就执行arr[finish] -= value，第二段增加了b<n的判断才执行减操作。
• 变量类型不同：第一段的n、m为int类型，第二段的n、m为long long类型。
• 头文件引入不同：第一段仅引入必要的iostream和vector头文件，第二段引入万能头bits/stdc++.h。

第二段代码触发段错误的原因 #

1. 栈溢出：栈内存的默认大小通常仅为1~8MB，远小于堆内存的可用空间。本题约束中n最大可达1e5，每个long long占8字节，数组总占用为800KB，若当前栈剩余空间不足，就会触发栈溢出，直接导致段错误。
2. 非法的变长数组初始化：变长数组不支持long long int x[n] = {0};的初始化方式，该语法仅适用于编译期长度固定的数组，错误的初始化会访问非法内存空间，触发段错误。

内容的提问来源于stack exchange，提问作者RAHUL MITTAL