N = 100
SIZE = N * N;

function fenwick_sum_primitive(arr, i) {
  sum = 0;
  while (i > 0) {
    sum = sum + arr[i];
    i = i - bitAnd(i, -i);
  }
  return sum;
}

function fenwick_sum(arr, i, j) {
  if (i == 1) {
    return fenwick_sum_primitive(arr, j);
  } else {
    return fenwick_sum_primitive(arr, j) - fenwick_sum_primitive(arr, i - 1);
  }
}

function fenwick_get(arr, i) {
  return fenwick_sum(arr, i, i);
}

function fenwick_add(arr, i, v) {
  while (i <= SIZE) {
    arr[i] = arr[i] + v;
    i = i + bitAnd(i, -i);
  }
}

function fenwick_set(arr, i, v) {
  current_val = fenwick_get(arr, i);
  fenwick_add(arr, i, v - current_val);
}

function arr_index_to_matrix_row(i) {
  return floor((i - 1) / N) + 1;
}

function arr_index_to_matrix_col(i) {
  return ((i - 1) %% N) + 1;
}

function matrix_index_to_arr_index(r, c) {
  return ((r - 1) * N + (c - 1)) + 1;
}

function binary_search(arr, v) {
  l = 1
  r = SIZE
  while (l <= r) {
    m = floor((l + r) / 2)
    result = fenwick_sum_primitive(arr, m)
    if (result >= v) {
      answer = m;
      r = m - 1;
    } else {
      l = m + 1;
    }
  }
  return answer;
}

function main() {
  // construct an identity matrix
  arr = array_of_length(SIZE) // 10000 elements, every entry is 0
  for (i = 1 to N) {
    arrIndex = matrix_index_to_arr_index(i, i)
    fenwick_add(arr, arrIndex, 1);
  }

  // calculate
  for (t = 1 to 10000000) {
    sum = fenwick_sum_primitive(arr, SIZE);
    x = random(sum) // random from 1 to sum
    k = binary_search(arr, x)

    r = arr_index_to_matrix_row(k)
    c = arr_index_to_matrix_col(k)

    // this should use the fenwick_set and matrix_index_to_arr_index function
    pro_function(arr, r, c);
  }

  for (r = 1 to N) {
    for (c = 1 to N) {
      print(fenwick_get(arr, matrix_index_to_arr_index(r, c)))
    }
    print_newline()
  }
}