# O(nlogn) C++ Segment Tree

• ``````class Solution {
public:
int n;
vector<int> height, lazy;

void push_up(int i) {
height[i] = max(height[i*2], height[i*2+1]);
}

void push_down(int i) {
if (lazy[i]) {
lazy[i*2] = lazy[i*2+1] = lazy[i];
height[i*2] = height[i*2+1] = lazy[i];
lazy[i] = 0;
}
}

void update(int i, int l, int r, int L, int R, int val) {
if (L <= l && r <= R) {
height[i] = val;
lazy[i] = val;
return;
}
push_down(i);
int mid = l + (r-l)/2;
if (L < mid) update(i*2, l, mid, L, R, val);
if (R > mid) update(i*2+1, mid, r, L, R, val);
push_up(i);
}

int query(int i, int l, int r, int L, int R) {
if (L <= l && r <= R) return height[i];
push_down(i);
int res = 0;;
int mid = l + (r-l)/2;
if (L < mid) res = max(res, query(i*2, l, mid, L, R));
if (R > mid) res = max(res, query(i*2+1, mid, r, L, R));
return res;
}

vector<int> fallingSquares(vector<pair<int, int>>& positions) {
vector<int> a;
for (auto& p : positions) {
a.push_back(p.first);
a.push_back(p.first+p.second);
}
sort(a.begin(), a.end());
n = unique(a.begin(), a.end()) - a.begin();
a.resize(n);

height.resize(n<<2, 0);
lazy.resize(n<<2, 0);
vector<int> res;
for (auto& p : positions) {
int l = lower_bound(a.begin(), a.end(), p.first) - a.begin();
int r = lower_bound(a.begin(), a.end(), p.first+p.second) - a.begin();
int maxh = query(1, 0, n, l, r);
update(1, 0, n, l, r, maxh+p.second);
res.push_back(query(1, 0, n, 0, n));
}
return res;
}
};
``````

• Here's a similar idea but with iteration instead of recursion:

``````struct Tree {
Tree(int n) {
this->n = n;
t.assign(2*n, 0);
d.assign(n, 0);
p.assign(n, false);
}

int n;
vector<int> t;
// Whether there are changes pending to be pushed down at node i.
vector<bool> p;
// If p[i] is true, d[i] contains the changes pending to be pushed down at node i.
vector<int> d;

// Get max between [l, r).
int get(int l, int r) {
assert(l < r);
l += n, r += n;
push(l);
push(r - 1);
int best = INT_MIN;
for (; l < r; l >>= 1, r >>= 1) {
if (l&1) best = max(best, t[l++]);
if (r&1) best = max(t[--r], best);
}
return best;
}

// Set all elements between [l, r) to be X.
void update(int l, int r, int value) {
assert(l < r);
l += n, r += n;
int l0 = l, r0 = r;
push(l0);
push(r0 - 1);
for (; l < r; l >>= 1, r >>= 1) {
if (l&1) overwrite(l++, value);
if (r&1) overwrite(--r, value);
}
refresh(l0);
refresh(r0 - 1);
}

private:
// Pushes down all changes from all ancestors of p.
void push(int u) {
if (u > 1) push(u >> 1);
if (u < n and p[u]) {
overwrite(u << 1, d[u]);
overwrite(u << 1 | 1, d[u]);
p[u] = false;
}
}

// Updates the given node with the given value.
void overwrite(int u, int value) {
t[u] = value;
if (u < n) {
p[u] = true;
d[u] = value;
}
}

// Assumes u has changed, so refreshes all of its parents.
void refresh(int u) {
for (u >>= 1; u > 0; u >>= 1) {
if (!p[u]) {
t[u] = max(t[u << 1], t[u << 1 | 1]);
}
}
}
};

int compress(const vector<int> &x, int value) {
return lower_bound(x.begin(), x.end(), value) - x.begin();
}

class Solution {
public:
vector<int> fallingSquares(const vector<pair<int, int>>& positions) {
int n = positions.size();
vector<int> x;
for (int i = 0; i < n; ++i) {
x.push_back(positions[i].first);
x.push_back(positions[i].first + positions[i].second);
}
sort(x.begin(), x.end());
unique(x.begin(), x.end());
int m = x.size();
Tree t(m);

vector<int> ans;
for (int i = 0; i < n; ++i) {
int left = positions[i].first;
int side = positions[i].second;

int l = compress(x, left);
int r = compress(x, left + side);

int base = t.get(l, r);
t.update(l, r, base + side);

ans.push_back(t.get(0, m));
}
return ans;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.