### PROBLEM LINK:

### DIFFICULTY:

EASY

### PREREQUISITES:

### PROBLEM:

Given a set of *n* points, we have to process the following two queries

- Update i, x, y : Update the
*ith*point to (x,y) - Query l, r : Print the maximum Manhattan distance between two points which lie between
*l*to*r*.

### EXPLANATION:

Lets consider a different problem in which we have only one query and no updates. In this problem we have to find two points P1(x1, y1) and P2(x2, y2) such that their Manhattan distance is maximized. Note that the Manhattan distance between any two points can be written as follows

dist(P1, P2) = |x1 - x2| + |y1 - y2| = max( x1 - x2 + y1 - y2, -x1 + x2 + y1 - y2, x1 - x2 + -y1 + y2, -x1 + x2 + -y1 + y2) ) = max( ( x1 + y1) - ( x2 + y2), (-x1 + y1) - (-x2 + y2), ( x1 - y1) - ( x2 - y2), (-x1 - y1) - (-x2 - y2) ) = max( f1(P1) - f1(P2), f2(P1) - f2(P2), f3(P1) - f3(P2), f4(P1) - f4(P2) ) where f1(P) = x+y, f2(P) = -x+y, f3(P) = x-y, f4(P) = -x-y

Note the last expression, not only it is free from any absolute signs but also it follows a pattern which is key to solving this problem. Formally we have to find

That is we have to find the point with maximum and minimum f1 value, subtract second from first and do this for f2, f3 and f4 as well and take the maximum among the four.

Now coming back to our original problem, here we have range query and point update, for this we will maintain 4 segment trees each corresponding to f1,f2,f3 and f4 containing the minimum and maximum values of f1,f2,f3 and f4. By this method querying and updating can be done in \mathcal{O}(\log (n)) time.

### RELATED PROBLEM:

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here

Tester’s solution can be found here

Editorialist’s solution can be found here