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

Question

I am coding a segment tree algorithm in which the nodes of the tree are arrays (it's supposed to represent the frequency of indices, it doesn't actually matter for my problem). Since I need to return an array when querying the tree, I figured I had to use a static variable. But that raises a problem: the total array is overwritten when the query goes down the tree because of recursion.

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

This is C++ and we are in 2020. Use 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 can be used like primitives. They can be copied, returned from functions and passed to functions by value.