Just for the record, this is my balancing BST solution built with array.

Long[][] bst;
void insert(long node) {
int i=0;
while (i<bst.length) {
if (bst[i]==null) {
bst[i]=new Long[]{node, 1l};
return;
}
if (bst[i][0]==node) {
bst[i][1]++;
return;
}
else if (bst[i][0]>node) i=2*i+1;
else i=2*i+2;
}
balance();
insert(node);
}
void balance() {
Long[][] copy = new Long[bst.length][];
int len = inorder(0, copy, 0);
for (int i=0;i<bst.length;i++) bst[i]=null;
build(copy, 0, len, 0);
}
void build(Long[][] copy, int s, int e, int root) {
if (s>=e) return;
int m = s+(e-s)/2;
bst[root] = copy[m];
build(copy, s, m, root*2+1);
build(copy, m+1, e, root*2+2);
}
int inorder(int i, Long[][] copy, int j) {
if (i>= bst.length || bst[i]==null) return j;
j = inorder(i*2+1, copy, j);
copy[j++] = bst[i];
j = inorder(i*2+2, copy, j);
return j;
}
int countFrom(int from, long l, long h) {
if (from >= bst.length|| bst[from]==null || l>h) return 0;
if (bst[from][0]>=l && bst[from][0]<=h) {
return bst[from][1].intValue() +
countFrom(from*2+1, l, bst[from][0]-1) +
countFrom(from*2+2, bst[from][0]+1, h);
} else if (bst[from][0]<l) {
return countFrom(from*2+2, l, h);
} else {
return countFrom(from*2+1, l, h);
}
}
public int countRangeSum(int[] nums, int lower, int upper) {
int ret = 0;
int len = 1;
while (len<nums.length) len<<=1;
bst = new Long[len<<1][];
long accDiff = 0;
for (int i=0;i<nums.length;i++) {
long n = nums[i];
accDiff += (-n);
n = accDiff + n;
insert(n);
ret += countFrom(0, lower+accDiff, upper+accDiff);
}
return ret;
}