Requisito previo: BIT (Binary Indexed Tree o Fenwick Tree) , BIT 2D
Dado un plano 2D, responda a las consultas Q, cada una del siguiente tipo:
- Insertar xy : inserta una coordenada de punto (x, y).
- Triángulo x1 y1 x2 y2 – Imprime el número de triángulos que se pueden formar, uniendo los puntos dentro del rectángulo, descrito por dos puntos (x1, y1) y (x2, y2), (x1, y1) es la parte inferior izquierda esquina mientras que (x2, y2) es la esquina superior derecha. Lo representaremos como {(x1, y1), (x2, y2)}. (Incluye los triángulos con áreas cero también en tu respuesta)
Ejemplo:
In the red rectangle there are 6 points inserted, when each of them is joined with a line with every other point, in all 20 triangles will be formed.
Digamos que de alguna manera tenemos un mecanismo para encontrar el número de puntos dentro de un rectángulo dado, dejemos que el número de puntos sea ‘m’ en una instancia.
El número de triángulos que se pueden formar con él son m C 3 (cada 3 puntos al unirlos formarán un triángulo); si tuviéramos que contar solo triángulos degenerados, tendríamos que restar el número de triángulos con áreas cero o formados a partir de puntos en la misma línea.
Ahora nos colamos en el mecanismo para encontrar el número de puntos en un rectángulo; supongamos que tenemos un mecanismo para encontrar el número de puntos dentro de un rectángulo.
Then number of points inside the rectangle
{(x1, y1), (x2, y2)} are,
P(x2, y2) -
P(x1 - 1, y2) -
P(x2, y1 - 1) +
P(x1 - 1, y1 - 1)
Where,
P(x, y) is number of triangles in rectangle
from (1, 1) to (x, y), i.e., {(1, 1), (x, y)}
Ahora, una vez que encontramos una forma de encontrar P(x, y), hemos terminado.
Si todas las consultas de inserción se hicieran primero, luego todas las consultas de triángulos, habría sido un trabajo fácil, podríamos mantener una tabla 2D para almacenar los puntos y la tabla [x] [y] contendría el número total de puntos en el rectángulo {(1, 1), (x, y)}.
Se puede crear usando el siguiente DP:
table[x][y] = table[x][y – 1] + table[x – 1][y] – table[x – 1][y – 1]
O nosotros puede usar un BIT 2D para insertar un punto y evaluar P(x, y). Para la visualización de un BIT 2D, consulte Top Coder . La imagen muestra un BIT 2D de 16 * 8 y el estado después de una inserción en (5, 3), los Nodes azules son los once que se actualizan.
Los BIT horizontales corresponden a 3 y almacenan 1 en el índice 3, 1 en el índice 4 y 1 en el índice 8; mientras que la representación vertical corresponde a qué BIT horizontales recibirán esa actualización, los que corresponden a 5, por lo que el BIT 5 desde abajo recibe una actualización, el BIT 6, luego el BIT 8 y luego el BIT 16.
Consideremos la actualización en un BIT 1D
update(BIT, x)
while ( x < maxn )
BIT[x] += val
x += x & -x
La actualización para 2D BIT es así:
update2DBIT(x, y)
// update BIT at index x (from bottom, in the image)
while ( x < maxn )
update(BIT[x], y)
x += x & -x
C++
// A C++ program implementing the above queries
#include<bits/stdc++.h>
#define maxn 2005
using namespace std;
// 2D Binary Indexed Tree. Note: global variable
// will have initially all elements zero
int bit[maxn][maxn];
// function to add a point at (x, y)
void update(int x, int y)
{
int y1;
while (x < maxn)
{
// x is the xth BIT that will be updated
// while y is the indices where an update
// will be made in xth BIT
y1 = y;
while ( y1 < maxn )
{
bit[x][y1]++;
y1 += ( y1 & -y1 );
}
// next BIT that should be updated
x += x & -x;
}
}
// Function to return number of points in the
// rectangle (1, 1), (x, y)
int query(int x, int y)
{
int res = 0, y1;
while (x > 0)
{
// xth BIT's yth node must be added to the result
y1 = y;
while (y1 > 0)
{
res += bit[x][y1];
y1 -= y1 & -y1;
}
// next BIT that will contribute to the result
x -= x & -x;
}
return res;
}
// (x1, y1) is the lower left and (x2, y2) is the
// upper right corner of the rectangle
int pointsInRectangle(int x1, int y1, int x2, int y2)
{
// Returns number of points in the rectangle
// (x1, y1), (x2, y2) as described in text above
return query(x2, y2) - query(x1 - 1, y2) -W
query(x2, y1 - 1) + query(x1 - 1, y1 - 1);
}
// Returns count of triangles with n points, i.e.,
// it returns nC3
int findTriangles(int n)
{
// returns pts choose 3
return (n * (n - 1) * (n - 2)) / 6;
}
//driver code
int main()
{
//inserting points
update(2, 2);
update(3, 5);
update(4, 2);
update(4, 5);
update(5, 4);
cout << "No. of triangles in the rectangle (1, 1)"
" (6, 6) are: "
<< findTriangles(pointsInRectangle(1, 1, 6, 6));
update(3, 3);
cout << "\nNo. of triangles in the rectangle (1, 1)"
" (6, 6) are: "
<< findTriangles( pointsInRectangle(1, 1, 6, 6));
return 0;
}
Java
// Java program implementing the above queries
import java.util.*;
class GFG
{
static int maxn = 2005;
// 2D Binary Indexed Tree. Note: global variable
// will have initially all elements zero
static int [][]bit = new int[maxn][maxn];
// function to add a point at (x, y)
static void update(int x, int y)
{
int y1;
while (x < maxn)
{
// x is the xth BIT that will be updated
// while y is the indices where an update
// will be made in xth BIT
y1 = y;
while ( y1 < maxn )
{
bit[x][y1]++;
y1 += (y1 & -y1);
}
// next BIT that should be updated
x += x & -x;
}
}
// Function to return number of points in the
// rectangle (1, 1), (x, y)
static int query(int x, int y)
{
int res = 0, y1;
while (x > 0)
{
// xth BIT's yth node
// must be added to the result
y1 = y;
while (y1 > 0)
{
res += bit[x][y1];
y1 -= y1 & -y1;
}
// next BIT that will contribute to the result
x -= x & -x;
}
return res;
}
// (x1, y1) is the lower left and (x2, y2) is the
// upper right corner of the rectangle
static int pointsInRectangle(int x1, int y1,
int x2, int y2)
{
// Returns number of points in the rectangle
// (x1, y1), (x2, y2) as described in text above
return query(x2, y2) - query(x1 - 1, y2) -
query(x2, y1 - 1) +
query(x1 - 1, y1 - 1);
}
// Returns count of triangles with n points, i.e.,
// it returns nC3
static int findTriangles(int n)
{
// returns pts choose 3
return (n * (n - 1) * (n - 2)) / 6;
}
// Driver Code
public static void main(String[] args)
{
// inserting points
update(2, 2);
update(3, 5);
update(4, 2);
update(4, 5);
update(5, 4);
System.out.print("No. of triangles in the " +
"rectangle (1, 1) (6, 6) are: " +
findTriangles(pointsInRectangle(1, 1, 6, 6)));
update(3, 3);
System.out.print("\nNo. of triangles in the " +
"rectangle (1, 1) (6, 6) are: " +
findTriangles( pointsInRectangle(1, 1, 6, 6)));
}
}
// This code is contributed by Rajput-Ji
Python3
# A Python3 program implementing
# the above queries
maxn = 2005
# 2D Binary Indexed Tree.
# Note: global variable
# will have initially all
# elements zero
bit = [[0 for j in range(maxn)]
for i in range(maxn)]
# function to add a point
# at(x, y)
def update(x, y):
y1 = 0
while (x < maxn):
# x is the xth BIT that will
# be updated while y is the
# indices where an update
# will be made in xth BIT
y1 = y
while (y1 < maxn):
bit[x][y1] += 1
y1 += (y1 & -y1)
# next BIT that should
# be updated
x += x & -x
# Function to return number of
# points in the rectangle(1, 1),
# (x, y)
def query(x, y):
res = 0
y1 = 0
while (x > 0):
# xth BIT's yth node must
# be added to the result
y1 = y
while (y1 > 0):
res += bit[x][y1]
y1 -= y1 & -y1
# next BIT that will contribute
# to the result
x -= x & -x
return res
# (x1, y1) is the lower left
# and (x2, y2) is the upper
# right corner of the rectangle
def pointsInRectangle(x1, y1,
x2, y2):
# Returns number of points
# in the rectangle (x1, y1),
# (x2, y2) as described in
# text above
return (query(x2, y2) - query(x1 - 1, y2) -
query(x2, y1 - 1) + query(x1 - 1, y1 - 1))
# Returns count of triangles with
# n points, i.e., it returns nC3
def findTriangles(n):
# returns pts choose 3
return ((n * (n - 1) *
(n - 2)) // 6)
# Driver code
if __name__ == "__main__":
# inserting points
update(2, 2)
update(3, 5)
update(4, 2)
update(4, 5)
update(5, 4)
print("No. of triangles in the " +
"rectangle (1, 1) (6, 6) are: ",
findTriangles(pointsInRectangle(1, 1,
6, 6)))
update(3, 3)
print("No. of triangles in the rectangle " +
"(1, 1) (6, 6) are:", findTriangles(
pointsInRectangle(1, 1, 6, 6)))
# This code is contributed by Rutvik_56
C#
// C# program implementing the above queries
using System;
class GFG
{
static int maxn = 2005;
// 2D Binary Indexed Tree. Note: global variable
// will have initially all elements zero
static int [,]bit = new int[maxn, maxn];
// function to add a point at (x, y)
static void update(int x, int y)
{
int y1;
while (x < maxn)
{
// x is the xth BIT that will be updated
// while y is the indices where an update
// will be made in xth BIT
y1 = y;
while (y1 < maxn)
{
bit[x, y1]++;
y1 += (y1 & -y1);
}
// next BIT that should be updated
x += x & -x;
}
}
// Function to return number of points in the
// rectangle (1, 1), (x, y)
static int query(int x, int y)
{
int res = 0, y1;
while (x > 0)
{
// xth BIT's yth node
// must be added to the result
y1 = y;
while (y1 > 0)
{
res += bit[x, y1];
y1 -= y1 & -y1;
}
// next BIT that will
// contribute to the result
x -= x & -x;
}
return res;
}
// (x1, y1) is the lower left and (x2, y2) is the
// upper right corner of the rectangle
static int pointsInRectangle(int x1, int y1,
int x2, int y2)
{
// Returns number of points in the rectangle
// (x1, y1), (x2, y2) as described in text above
return query(x2, y2) - query(x1 - 1, y2) -
query(x2, y1 - 1) +
query(x1 - 1, y1 - 1);
}
// Returns count of triangles with n points, i.e.,
// it returns nC3
static int findTriangles(int n)
{
// returns pts choose 3
return (n * (n - 1) * (n - 2)) / 6;
}
// Driver Code
public static void Main(String[] args)
{
// inserting points
update(2, 2);
update(3, 5);
update(4, 2);
update(4, 5);
update(5, 4);
Console.Write("No. of triangles in the " +
"rectangle (1, 1) (6, 6) are: " +
findTriangles(pointsInRectangle(1, 1, 6, 6)));
update(3, 3);
Console.Write("\nNo. of triangles in the " +
"rectangle (1, 1) (6, 6) are: " +
findTriangles( pointsInRectangle(1, 1, 6, 6)));
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// JavaScript program implementing the above queries
var maxn = 2005;
// 2D Binary Indexed Tree. Note: global variable
// will have initially all elements zero
var bit = Array(maxn).fill().map(()=>Array(maxn).fill(0));
// function to add a point at (x, y)
function update(x , y) {
var y1;
while (x < maxn) {
// x is the xth BIT that will be updated
// while y is the indices where an update
// will be made in xth BIT
y1 = y;
while (y1 < maxn) {
bit[x][y1]++;
y1 += (y1 & -y1);
}
// next BIT that should be updated
x += x & -x;
}
}
// Function to return number of points in the
// rectangle (1, 1), (x, y)
function query(x , y) {
var res = 0, y1;
while (x > 0) {
// xth BIT's yth node
// must be added to the result
y1 = y;
while (y1 > 0) {
res += bit[x][y1];
y1 -= y1 & -y1;
}
// next BIT that will contribute to the result
x -= x & -x;
}
return res;
}
// (x1, y1) is the lower left and (x2, y2) is the
// upper right corner of the rectangle
function pointsInRectangle(x1 , y1 , x2 , y2) {
// Returns number of points in the rectangle
// (x1, y1), (x2, y2) as described in text above
return query(x2, y2) - query(x1 - 1, y2) -
query(x2, y1 - 1) + query(x1 - 1, y1 - 1);
}
// Returns count of triangles with n points, i.e.,
// it returns nC3
function findTriangles(n) {
// returns pts choose 3
return (n * (n - 1) * (n - 2)) / 6;
}
// Driver Code
// inserting points
update(2, 2);
update(3, 5);
update(4, 2);
update(4, 5);
update(5, 4);
document.write("No. of triangles in the " +
"rectangle (1, 1) (6, 6) are: "
+ findTriangles(pointsInRectangle(1, 1, 6, 6)));
update(3, 3);
document.write("<br/>No. of triangles in the " +
"rectangle (1, 1) (6, 6) are: "
+ findTriangles(pointsInRectangle(1, 1, 6, 6)));
// This code contributed by gauravrajput1
</script>
Producción:
No of triangles in the rectangle (1, 1) (6, 6) are: 10 No of triangles in the rectangle (1, 1) (6, 6) are: 20
Complejidad de tiempo: para cada consulta de cualquier tipo: O (log (x) * log (y)) O de hecho: O (número de unos en representación binaria de x * número de unos en una representación binaria de y)
Complejidad de tiempo total: O(Q * log(maxX) * log(maxY)) Saumye Malhotra
contribuye con este artículo . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo para contribuir @geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks. Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA