The basic idea is do a insert from right most element in nums to the left most element.

At each insert(nums[i]), when we go right of the AVL tree, we add the count at root and size of left subtree. the sum is the val at res[i];

Three different point to a vanilla AVL tree.

- No delete need. So I make the node destructer delete its left and right.
- Add a subtree size field at each node, when we do rotate, we need to consider that.
- Add a count file at each node as there may be element in nums has same value.

This is not a smart solution. And R-B tree should be batter for this use case. Just a practice for coding.

BTW. I tired regular BST, the run time is the same as this one. Should more test case be added to make regular BST to be TLE?

Should OJ add the window size, So I can prictice the AVL or R-B tree delete?

```
struct node {
int val; // value
int height; // height of this node
int count; // number of num at this node
int size; // number of num at this subtree
node* left, *right;
node(int v): val(v), height(1), size(1), left(NULL), right(NULL), count(1) {}
~node() {
if (left) delete left;
if (right) delete right;
}
};
class tree {
node *root;
int count;
int height(node *cur) {
if (cur) {
return cur->height;
}
return 0;
}
int balance(node *cur) {
if (cur)
return height(cur->left) - height(cur->right);
return 0;
}
int size(node *cur) {
if (cur) {
return cur->size;
}
return 0;
}
node *right_r (node *p) {
node *c = p->left;
p->left = c->right;
c->right = p;
// height balance;
p->height = 1 + max(height(p->left), height(p->right));
c->height = 1 + max(height(c->left), height(c->right));
// size recal;
int all = p->size;
p->size -= c->count + size(c->left);
c->size = all;
return c;
}
node *left_r(node *p) {
node *c = p->right;
p->right = c->left;
c->left = p;
p->height = 1 + max(height(p->left), height(p->right));
c->height = 1 + max(height(c->left), height(c->right));
// size recal;
int all = p->size;
p->size -= c->count + size(c->right);
c->size = all;
return c;
}
node *insert_rec(node* cur, int val) {
if (cur==NULL) {
return new node(val);
}
cur->size++;
if (val < cur->val) {
cur->left = insert_rec(cur->left, val);
} else if (cur->val < val) {
cur->right = insert_rec(cur->right,val);
count+=cur->count + size(cur->left);
} else {
cur->count++;
count += size(cur->left);
return cur;
}
cur->height = 1 + max(height(cur->left), height(cur->right));
int b = balance(cur);
if (b>1) {
if (val < cur->val) {
return right_r(cur);
} else {
cur->left = left_r(cur->left);
return right_r(cur);
}
} else if (b<-1) {
if (cur->val < val) {
return left_r(cur);
} else {
cur->right = right_r(cur->right);
return left_r(cur);
}
}
return cur;
}
public:
tree(): root(NULL) {}
~tree() {
delete root;
}
int insert(int val) {
count = 0;
root = insert_rec(root, val);
return count;
}
};
class Solution {
tree avl_tree;
public:
vector<int> countSmaller(vector<int>& nums) {
int n = nums.size();
vector<int> res(n);
if (n==0) return res;
for (int i = n-1; i>=0; --i) {
res[i] = avl_tree.insert(nums[i]);
}
return res;
}
};
```