由于递归，函数返回的静态数组被覆盖

Question

我正在编写一个线段树算法，其中树的节点是数组（它应该表示索引的频率，它实际上对我的问题并不重要）。因为在查询树时我需要 return 一个数组，所以我想我必须使用一个静态变量。但这引发了一个问题：由于递归，当查询沿着树向下移动时，total 数组被覆盖。

int* query(int tree[][9], int i, int j, int pos, int qi, int qj){
  if(qi <= i && qj >= j){
    return tree[pos];
  }else if(qi > j || qj < i){
    static int empty[9];
    for (size_t k = 0; k < 9; k++) empty[k] = 0;
    return empty;
  }

  int mid = (i+j)/2;

  int *left  = query(tree,     i, mid, 2*pos+1, qi, qj);
  int *right = query(tree, mid+1,   j, 2*pos+2, qi, qj);

  static int total[9];

  for (size_t k = 0; k < 9; k++) {
    total[k] = left[k] + right[k];
  }

  return total;
}

Answer 1

这是 C++，现在是 2020 年。使用 std::array or std::vector

auto query(std::array<std::array<int, 9>, 9> const &tree, int i, int j, int pos, int qi, int qj){
  if(qi <= i && qj >= j){
    return tree[pos];
  }else if(qi > j || qj < i){
    return std::array<int, 9>{};
  }

  int const mid = (i+j)/2;

  auto const left  = query(tree,     i, mid, 2*pos+1, qi, qj);
  auto const right = query(tree, mid+1,   j, 2*pos+2, qi, qj);

  std::array<int, 9> total;

  for (std::size_t k = 0; k < 9; k++) {
    total[k] = left[k] + right[k];
  }

  return total;
}

std::arrays 可以像基元一样使用。它们可以被复制、从函数返回并按值传递给函数。

Answer 2

正如 Thomas 指出的那样，您可以使用 std::vector 或 std::array，但如果您真的想使用老式数组，我建议您传递数组而不是 return 值但是作为参数（指向它的指针或者更好的参考）是这样的：

void query(int tree[][9], int i, int j, int pos, int qi, int qj, int (&ret)[9]])

你可以在函数中填充数组。

也有可能 return 指向数组的指针，但这可能会导致内存管理混乱。

由于递归，函数返回的静态数组被覆盖

Static array returned by a function is being overwritten because of recursion

c++

algorithm

recursion

pointers

segment-tree