如果最初有一个空集，并对其进行了大量查询，则每个查询都可能是以下类型：
null
- 插入 –插入新元素“x”。
- 删去 –删除现有元素“x”。
- 中值的 –打印集合中当前数字的中间元素
例子：
Input : Insert 1 Insert 4 Insert 7 Median Output : The first three queries should insert 1, 4 and 7 into an empty set. The fourth query should return 4 (median of 1, 4, 7).
出于解释目的，我们假设以下情况，但这些假设不是本文讨论的方法的局限性： 1.在任何情况下，所有元素都是不同的，也就是说，它们都不会出现一次以上。 2.仅当集合中有奇数个元素时，才会进行“中值”查询。（如果是偶数，我们需要在片段树上进行两次查询） 3.集合中的元素范围为1到+10^6。
方法1（天真） 在naive实现中，我们可以在O（1）中执行前两个查询，但在O（max_elem）中执行最后一个查询，其中max_elem是所有时间（包括删除的元素）中的最大元素。
让我们假设一个数组 计数[] （大小为10^6+1）以保持子集中每个元素的计数。以下是3个查询的简单且自解释的算法： 插入x查询：
count[x]++; if (x > max_elem) max_elem = x; n++;
删除x查询：
if (count[x] > 0) count[x]--; n--;
中值查询：
sum = 0; i = 0; while( sum <= n / 2 ) { i++; sum += count[i]; } median = i; return median;
数组计数[]的图示，表示集合{1,4,7,8,9}，中值元素为’7’：
![图片[1]-高效地设计集合上的插入、删除和中值查询-yiteyi-C++库](https://www.yiteyi.com/wp-content/uploads/geeks/geeks_efficiently-designed.png)
“中值”查询旨在查找数组中的第（n+1）/2个“1”，在本例中是第3个“1”；现在我们使用一个段树来做同样的事情。 方法2（使用 分段树 ) 我们做一个 分段树 存储区间总和，其中区间[a，b]表示集合中当前[a，b]范围内的元素数。例如，如果我们考虑上面的示例，查询（3, 7）返回2，查询（4, 4）返回1，查询（5, 5）返回0。
Insert和delete查询很简单，都可以使用函数更新（int x，int diff）实现（在索引“x”处添加“diff”）
算法
// adds ‘diff’ at index ‘x’update(node, a, b, x, diff) // If leaf node If a == b and a == x segmentTree[node] += diff // If non-leaf node and x lies in its range If x is in [a, b] // Update children recursively update(2*node, a, (a + b)/2, x, diff) update(2*node + 1, (a + b)/2 + 1, b, x, diff) // Update node segmentTree[node] = segmentTree[2 * node] + segmentTree[2 * node + 1]
上面的递归函数在 O（对数（最大值）） （在本例中，max_elem为10^6），用于插入和删除以下调用：
- 使用更新（1,0,10^6,x,1）完成插入“x”。请注意，树的根被传递，开始索引被传递为0，结束索引被传递为10^6，这样所有包含x的范围都会被更新。
- 使用更新（1,0,10^6,x，-1）删除“x”。请注意，树的根被传递，开始索引被传递为0，结束索引被传递为10^6，这样所有包含x的范围都会被更新。
现在，用kth’1’查找索引的函数，在这种情况下，k始终是（n+1）/2，这与二进制搜索非常相似，你可以把它看作是段树上的递归二进制搜索函数。
让我们举一个例子来理解，我们的集合目前有元素{1,4,7,8,9}，因此由下面的段树表示。
![图片[2]-高效地设计集合上的插入、删除和中值查询-yiteyi-C++库](https://www.yiteyi.com/wp-content/uploads/geeks/geeks_efficiently-designed_1.png)
如果我们在一个非叶节点上，我们确定它有两个子节点，我们看左边的子节点是否有更多或相等数量的1作为“k”，如果是，我们确定我们的索引位于左边的子树，否则，如果左边的子树的数量少于k，那么我们确定我们的索引位于右边的子树。我们递归地这样做以达到我们的索引，然后从那里返回它。
算法
1.findKth(node, a, b, k)2. If a != b 3. If segmentTree[ 2 * node ] >= k4. return findKth(2*node, a, (a + b)/2, k)5. else6. return findKth(2*node + 1, (a + b)/2 + 1, b, k - segmentTree[ 2 * node ])7. else8. return a
上面的递归函数在 O（对数（最大值）） .
C++
// A C++ program to implement insert, delete and // median queries using segment tree #include<bits/stdc++.h> #define maxn 3000005 #define max_elem 1000000 using namespace std; // A global array to store segment tree. // Note: Since it is global, all elements are 0. int segmentTree[maxn]; // Update 'node' and its children in segment tree. // Here 'node' is index in segmentTree[], 'a' and // 'b' are starting and ending indexes of range stored // in current node. // 'diff' is the value to be added to value 'x'. void update( int node, int a, int b, int x, int diff) { // If current node is a leaf node if (a == b && a == x ) { // add 'diff' and return segmentTree[node] += diff; return ; } // If current node is non-leaf and 'x' is in its // range if (x >= a && x <= b) { // update both sub-trees, left and right update(node*2, a, (a + b)/2, x, diff); update(node*2 + 1, (a + b)/2 + 1, b, x, diff); // Finally update current node segmentTree[node] = segmentTree[node*2] + segmentTree[node*2 + 1]; } } // Returns k'th node in segment tree int findKth( int node, int a, int b, int k) { // non-leaf node, will definitely have both // children; left and right if (a != b) { // If kth element lies in the left subtree if (segmentTree[node*2] >= k) return findKth(node*2, a, (a + b)/2, k); // If kth one lies in the right subtree return findKth(node*2 + 1, (a + b)/2 + 1, b, k - segmentTree[node*2]); } // if at a leaf node, return the index it stores // information about return (segmentTree[node])? a : -1; } // insert x in the set void insert( int x) { update(1, 0, max_elem, x, 1); } // delete x from the set void delete ( int x) { update(1, 0, max_elem, x, -1); } // returns median element of the set with odd // cardinality only int median() { int k = (segmentTree[1] + 1) / 2; return findKth(1, 0, max_elem, k); } // Driver code int main() { insert(1); insert(4); insert(7); cout << "Median for the set {1,4,7} = " << median() << endl; insert(8); insert(9); cout << "Median for the set {1,4,7,8,9} = " << median() << endl; delete (1); delete (8); cout << "Median for the set {4,7,9} = " << median() << endl; return 0; } |
JAVA
// A Java program to implement insert, delete and // median queries using segment tree import java.io.*; class GFG{ public static int maxn = 3000005 ; public static int max_elem = 1000000 ; // A global array to store segment tree. // Note: Since it is global, all elements are 0. public static int [] segmentTree = new int [maxn]; // Update 'node' and its children in segment tree. // Here 'node' is index in segmentTree[], 'a' and // 'b' are starting and ending indexes of range stored // in current node. // 'diff' is the value to be added to value 'x'. public static void update( int node, int a, int b, int x, int diff) { // If current node is a leaf node if (a == b && a == x ) { // Add 'diff' and return segmentTree[node] += diff; return ; } // If current node is non-leaf and 'x' // is in its range if (x >= a && x <= b) { // Update both sub-trees, left and right update(node * 2 , a, (a + b) / 2 , x, diff); update(node * 2 + 1 , (a + b) / 2 + 1 , b, x, diff); // Finally update current node segmentTree[node] = segmentTree[node * 2 ] + segmentTree[node * 2 + 1 ]; } } // Returns k'th node in segment tree public static int findKth( int node, int a, int b, int k) { // Non-leaf node, will definitely have both // children; left and right if (a != b) { // If kth element lies in the left subtree if (segmentTree[node * 2 ] >= k) { return findKth(node * 2 , a, (a + b) / 2 , k); } // If kth one lies in the right subtree return findKth(node * 2 + 1 , (a + b) / 2 + 1 , b, k - segmentTree[node * 2 ]); } // If at a leaf node, return the index it stores // information about return (segmentTree[node] != 0 ) ? a : - 1 ; } // Insert x in the set public static void insert( int x) { update( 1 , 0 , max_elem, x, 1 ); } // Delete x from the set public static void delete( int x) { update( 1 , 0 , max_elem, x, - 1 ); } // Returns median element of the set // with odd cardinality only public static int median() { int k = (segmentTree[ 1 ] + 1 ) / 2 ; return findKth( 1 , 0 , max_elem, k); } // Driver code public static void main(String[] args) { insert( 1 ); insert( 4 ); insert( 7 ); System.out.println( "Median for the set {1,4,7} = " + median()); insert( 8 ); insert( 9 ); System.out.println( "Median for the set {1,4,7,8,9} = " + median()); delete( 1 ); delete( 8 ); System.out.println( "Median for the set {4,7,9} = " + median()); } } // This code is contributed by avanitrachhadiya2155 |
Python3
# A Python3 program to implement insert, delete and # median queries using segment tree maxn = 3000005 max_elem = 1000000 # A global array to store segment tree. # Note: Since it is global, all elements are 0. segmentTree = [ 0 for i in range (maxn)] # Update 'node' and its children in segment tree. # Here 'node' is index in segmentTree[], 'a' and # 'b' are starting and ending indexes of range stored # in current node. # 'diff' is the value to be added to value 'x'. def update(node, a, b, x, diff): global segmentTree # If current node is a leaf node if (a = = b and a = = x ): # add 'diff' and return segmentTree[node] + = diff return # If current node is non-leaf and 'x' is in its # range if (x > = a and x < = b): # update both sub-trees, left and right update(node * 2 , a, (a + b) / / 2 , x, diff) update(node * 2 + 1 , (a + b) / / 2 + 1 , b, x, diff) # Finally update current node segmentTree[node] = segmentTree[node * 2 ] + segmentTree[node * 2 + 1 ] # Returns k'th node in segment tree def findKth(node, a, b, k): global segmentTree # non-leaf node, will definitely have both # children left and right if (a ! = b): # If kth element lies in the left subtree if (segmentTree[node * 2 ] > = k): return findKth(node * 2 , a, (a + b) / / 2 , k) # If kth one lies in the right subtree return findKth(node * 2 + 1 , (a + b) / / 2 + 1 , b, k - segmentTree[node * 2 ]) # if at a leaf node, return the index it stores # information about return a if (segmentTree[node]) else - 1 # insert x in the set def insert(x): update( 1 , 0 , max_elem, x, 1 ) # delete x from the set def delete(x): update( 1 , 0 , max_elem, x, - 1 ) # returns median element of the set with odd # cardinality only def median(): k = (segmentTree[ 1 ] + 1 ) / / 2 return findKth( 1 , 0 , max_elem, k) # Driver code if __name__ = = '__main__' : insert( 1 ) insert( 4 ) insert( 7 ) print ( "Median for the set {1,4,7} =" ,median()) insert( 8 ) insert( 9 ) print ( "Median for the set {1,4,7,8,9} =" ,median()) delete( 1 ) delete( 8 ) print ( "Median for the set {4,7,9} =" ,median()) # This code is contributed by mohit kumar 29 |
C#
// A C# program to implement insert, delete // and median queries using segment tree using System; class GFG{ public static int maxn = 3000005; public static int max_elem = 1000000; // A global array to store segment tree. // Note: Since it is global, all elements are 0. public static int [] segmentTree = new int [maxn]; // Update 'node' and its children in segment tree. // Here 'node' is index in segmentTree[], 'a' and // 'b' are starting and ending indexes of range stored // in current node. // 'diff' is the value to be added to value 'x'. public static void update( int node, int a, int b, int x, int diff) { // If current node is a leaf node if (a == b && a == x) { // Add 'diff' and return segmentTree[node] += diff; return ; } // If current node is non-leaf and 'x' // is in its range if (x >= a && x <= b) { // Update both sub-trees, left and right update(node * 2, a, (a + b) / 2, x, diff); update(node * 2 + 1, (a + b) / 2 + 1, b, x, diff); // Finally update current node segmentTree[node] = segmentTree[node * 2] + segmentTree[node * 2 + 1]; } } // Returns k'th node in segment tree public static int findKth( int node, int a, int b, int k) { // Non-leaf node, will definitely have both // children; left and right if (a != b) { // If kth element lies in the left subtree if (segmentTree[node * 2] >= k) { return findKth(node * 2, a, (a + b) / 2, k); } // If kth one lies in the right subtree return findKth(node * 2 + 1, (a + b) / 2 + 1, b, k - segmentTree[node * 2]); } // If at a leaf node, return the index it // stores information about if (segmentTree[node] != 0) { return a; } else { return -1; } } // Insert x in the set public static void insert( int x) { update(1, 0, max_elem, x, 1); } // Delete x from the set public static void delete( int x) { update(1, 0, max_elem, x, -1); } // Returns median element of the set // with odd cardinality only public static int median() { int k = (segmentTree[1] + 1) / 2; return findKth(1, 0, max_elem, k); } // Driver code static public void Main() { insert(1); insert(4); insert(7); Console.WriteLine( "Median for the set {1,4,7} = " + median()); insert(8); insert(9); Console.WriteLine( "Median for the set {1,4,7,8,9} = " + median()); delete(1); delete(8); Console.WriteLine( "Median for the set {4,7,9} = " + median()); } } // This code is contributed by rag2127 |
Javascript
<script> // A Javascript program to implement insert, delete and // median queries using segment tree let maxn = 3000005; let max_elem = 1000000; // A global array to store segment tree. // Note: Since it is global, all elements are 0. let segmentTree = new Array(maxn); for (let i=0;i<maxn;i++) { segmentTree[i]=0; } // Update 'node' and its children in segment tree. // Here 'node' is index in segmentTree[], 'a' and // 'b' are starting and ending indexes of range stored // in current node. // 'diff' is the value to be added to value 'x'. function update(node,a,b,x,diff) { // If current node is a leaf node if (a == b && a == x ) { // Add 'diff' and return segmentTree[node] += diff; return ; } // If current node is non-leaf and 'x' // is in its range if (x >= a && x <= b) { // Update both sub-trees, left and right update(node * 2, a, Math.floor((a + b) / 2), x, diff); update(node * 2 + 1, Math.floor((a + b) / 2) + 1, b, x, diff); // Finally update current node segmentTree[node] = segmentTree[node * 2] + segmentTree[node * 2 + 1]; } } // Returns k'th node in segment tree function findKth(node,a,b,k) { // Non-leaf node, will definitely have both // children; left and right if (a != b) { // If kth element lies in the left subtree if (segmentTree[node * 2] >= k) { return findKth(node * 2, a, Math.floor((a + b) / 2), k); } // If kth one lies in the right subtree return findKth(node * 2 + 1, Math.floor((a + b) / 2) + 1, b, k - segmentTree[node * 2]); } // If at a leaf node, return the index it stores // information about return (segmentTree[node] != 0) ? a : -1; } // Insert x in the set function insert(x) { update(1, 0, max_elem, x, 1); } // Delete x from the set function delet(x) { update(1, 0, max_elem, x, -1); } // Returns median element of the set // with odd cardinality only function median() { let k = (segmentTree[1] + 1) / 2; return findKth(1, 0, max_elem, k); } // Driver code insert(1); insert(4); insert(7); document.write( "Median for the set {1,4,7} = " + median()+ "<br>" ); insert(8); insert(9); document.write( "Median for the set {1,4,7,8,9} = " + median()+ "<br>" ); delet(1); delet(8); document.write( "Median for the set {4,7,9} = " + median()+ "<br>" ); // This code is contributed by unknown2108 </script> |
输出：
Median for the set {1,4,7} = 4Median for the set {1,4,7,8,9} = 7Median for the set {4,7,9} = 7
结论： 这三个查询都会自动运行 O（对数（最大值）） ，在这种情况下，max_elem=10^6，所以log（max_elem）大约等于20。 段树使用 O（马克斯·埃利姆） 空间
如果没有删除查询，这个问题也可以用著名的算法解决 在这里 .
本文由 萨乌米·马尔霍特拉 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
