Problem link: loj 1266
Technique: Binary Indexed Tree
If you don't know about Binary Indexed Tree, first learn it. You can also check BIT here BIT
Given two types of query,
1
4
0 1 1
0 2 6
1 1 1 6 6
1 2 2 5 5
We added D because, while subtracting B and C, D got subtracted twice. So we need to balance it by adding. Hope you understand what we need to do here.
Given two types of query,
- 0 x y: we got a new point at co-ordinate (x,y) [ if already a point exist in the same co-ordinate, this query does nothing ]
- 1 x1 y1 x2 y2: we are given a rectangle whose lower left co-ordinate is (x1, y1) and upper-right corner is (x2, y2); your task is to find the number of points, given so far, that lie inside this rectangle. You can assume that (x1 < x2, y1 < y2).
1
4
0 1 1
0 2 6
1 1 1 6 6
1 2 2 5 5
We got two points (1,1) and (2,6), let's plot these points:
Now let's see the first query, we have to find how many points are inside (1,1) and (6,6). We will call out query_sum function with parameter (6,6), And this will cover the whole area from (1,1) to (6,6) and we will get output = 2
Ok, for the second query we need to find points inside (2,2) and (5,5). We will call our query_sum function with (5,5) and the selected area would be like this:
Ok, for the second query we need to find points inside (2,2) and (5,5). We will call our query_sum function with (5,5) and the selected area would be like this:
But we have some extra area here as our query starts from (2,2). So we need to remove those extra area. Basically we need to calculate our desired area as follow:
area = query_sum(x2,y2)-query_sum(x1-1,y2-1)-query_sum(x2-1,y1-1)+query_sum(x1-1,y1-1)
Let's see how does it look, Here:
A = query_sum(x2,y2)
B = query_sum(x1-1,y2-1)
C = query_sum(x2-1,y1-1)
D = query_sum(x1-1,y1-1)
We added D because, while subtracting B and C, D got subtracted twice. So we need to balance it by adding. Hope you understand what we need to do here.
Code:
