先决条件： 位（二元索引树或Fenwick树） , 二维位 给定一个二维平面，回答以下类型的Q查询：
null
- 插入x y –插入点（x，y）坐标。
- 三角形x1 y1 x2 y2 –打印通过连接矩形内的点可以形成的三角形的数量，由两点（x1，y1）和（x2，y2）描述，（x1，y1）是左下角，而（x2，y2）是右上角。我们将它表示为{（x1，y1），（x2，y2）}。（答案中也包括面积为零的三角形）
例子：
![图片[1]-用BIT计算矩形空间中的三角形-yiteyi-C++库](https://www.yiteyi.com/wp-content/uploads/geeks/geeks_counting-triangles.png)
In the red rectangle there are 6 points inserted, when each of them is joined with a line with everyother point, in all 20 triangles will be formed.
假设我们有一种机制，可以找到给定矩形内的点数，在一个实例中，点数为’m’。 可以用它形成的三角形的数量是 M C 3. （连接时，每3个点将形成一个三角形）；如果我们必须只计算退化三角形，我们必须减去面积为零或由同一直线上的点形成的三角形的数量。 现在，我们潜入这个机制，找到矩形中的点数；让我们假设我们有一种机制来计算矩形内的点数。
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 rectanglefrom (1, 1) to (x, y), i.e., {(1, 1), (x, y)}
现在，一旦我们找到了求P（x，y）的方法，我们就完成了。 如果先进行所有的插入查询，然后进行所有的三角形查询，这将是一项简单的工作，我们可以维护一个2D表格来存储点，表格[x][y]将包含矩形{（1，1），（x，y）}中的点的总数。 可以使用以下DP创建： 表[x][y]=表[x][y-1]+表[x-1][y]-表[x-1][y-1] 或者我们可以使用2D位插入一个点并计算P（x，y）。有关二维位的可视化，请参阅 顶级编码器 图中显示了一个16*8的2D位，以及在（5,3）处插入后的状态，蓝色节点是更新的ONCE。 水平位对应于3，并在索引3处存储1，在索引4处存储1，在索引8处存储1；垂直表示对应于将接收更新的水平位，而对应于5的水平位，因此从底部开始的第5位将得到更新，第6位，然后是第8位，然后是第16位。 让我们考虑一下在1D位中的更新。
update(BIT, x) while ( x < maxn ) BIT[x] += val x += x & -x
2D位的更新如下所示：
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 << "No. 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( "No. 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( "No. 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> |
输出：
No of triangles in the rectangle (1, 1) (6, 6) are: 10No of triangles in the rectangle (1, 1) (6, 6) are: 20
时间复杂性： 对于任一类型的查询： O（对数（x）*对数（y）） 事实上： O（x的二进制表示中的个数*y的二进制表示中的个数） 总时间复杂度： O（Q*log（maxX）*log（maxY）） 本文由 萨乌米·马尔霍特拉 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
