Actually, I was trying to implement a segment tree by what I remember (I had roughly heard of segment tree 3 years ago). But after my finish and seeing the solution, I find what I had implemented is a balanced binary search tree with height as balance condition... and I want comments and discussion.

The tree I used is a binary search tree where each node represents a closed interval [`ends[0]`

, `ends[1]`

] that all points in it is at `height`

.

The tree is also a balanced tree that use `height`

as balance condition, which means a subtree is "balanced" until its `root`

has the biggest `height`

. A unbalanced tree will be rotated to balance, the rotate operation is similar to that of AVL tree.

The two features of the tree means we can find the interval that the new square will be stuck in one turn of binary search.

```
struct segment {
int ends[2]; //all points in [ends[0], ends[1]] is at height
int height;
struct segment *left, *right;
};
#define INF 1000000000
struct segment *newSegment(int l, int r, int h) {
struct segment *s = (struct segment *) malloc(sizeof(struct segment));
s->ends[0] = l;
s->ends[1] = r;
s->height = h;
s->left = s->right = NULL;
return s;
}
// typical recursion searching of binary search tree
struct segment *findSegment(struct segment *root, int l, int r) {
if (root->ends[0] > r)
return findSegment(root->left, l, r);
if (root->ends[1] < l)
return findSegment(root->right, l, r);
return root;
}
// balance a unbalanced tree in recursion (in a bottom-up way)
void sortSegment(struct segment **root, int l, int r) {
struct segment *p = (*root);
if (p->ends[0] > r) {
sortSegment(&(p->left), l, r); // balance left subtree
if (p->height < p->left->height) { // left son is higher than root, rotate right
(*root) = p->left;
p->left = p->left->right;
(*root)->right = p;
}
} else if (p->ends[1] < l) {
sortSegment(&(p->right), l, r);
if (p->height < p->right->height) {
(*root) = p->right;
p->right = p->right->left;
(*root)->left = p;
}
}
}
int insertSegment(struct segment **root, int pos, int len) {
int l = pos, r = pos + len - 1;
// find the first segment 'ptr' that the new square stick
struct segment *ptr = findSegment(*root, l, r);
int h = ptr->height + len;
// because of symmetry, we just consider left endpoint of the new square
// three cases: the left endpoint is 'left to / same as / right to' that of 'ptr'
// and we truncate the 'ptr' to turn 'left to / right to' cases into 'same as'.
// case 0: right to, 'ptr' is split and new segment is inserted
if (ptr->ends[0] < l) {
struct segment *s0 = newSegment(ptr->ends[0], l - 1, ptr->height);
s0->left = ptr->left;
ptr->left = s0;
// case 1: left to, the left subtree of 'ptr' is truncated
} else if (ptr->ends[0] > l) {
struct segment *s0 = ptr->left;
while (s0 != NULL) {
if (s0->ends[0] < l)
break;
// to do: call free()
s0 = s0->left;
}
ptr->left = s0;
while (s0 != NULL) {
if (s0->ends[1] >= l)
break;
s0 = s0->right;
}
if (s0 != NULL) {
s0->ends[1] = l - 1;
s0->right = NULL;
}
}
if (ptr->ends[1] > r) {
struct segment *s1 = newSegment(r + 1, ptr->ends[1], ptr->height);
s1->right = ptr->right;
ptr->right = s1;
} else if (ptr->ends[1] > r) {
struct segment *s1 = ptr->right;
while (s1 != NULL) {
if (s1->ends[1] > r)
break;
// to do: call free()
s1 = s1->right;
}
ptr->right = s1;
while (s1 != NULL) {
if (s1->ends[0] <= r)
break;
s1 = s1->left;
}
if (s1 != NULL) {
s1->ends[0] = r + 1;
s1->left = NULL;
}
}
ptr->ends[0] = l;
ptr->ends[1] = r;
ptr->height = h;
// rebalance the tree
sortSegment(root, l, r);
return h;
}
int *fallingSquares(int **positions, int positionsRowSize, int positionsColSize, int *returnSize) {
(*returnSize) = positionsRowSize;
int *heights = (int *)malloc(sizeof(int) * positionsRowSize);
struct segment *root = newSegment(0, INF, 0);
int i, maxh = 0;
for (i = 0; i < positionsRowSize; i++) {
int h = insertSegment(&root, positions[i][0], positions[i][1]);
maxh = (h > maxh) ? h : maxh;
heights[i] = maxh;
}
return heights;
}
```