fork download
copy 
  1. /**
  2.  * KthElement is a class for maintain a set of elements (allow repeated values) like a BST using segment tree structure
  3.  * Complexity: O(logN) per operation
  4.  * 
  5.  * Autor: Alexis Hernandez
  6. **/
  7.  
  8. public class KthElement	{
  9.  
  10. 	int N;
  11. 	int [] cnt;
  12. 	/**
  13. 	 * 
  14. 	 * @param numOfElements = how many different elements are allowed [0 ... numOfElements)
  15. 	**/
  16. 	KthElement(int numOfElements)	{
  17.  
  18. 		N = Integer.highestOneBit(numOfElements);
  19. 		if	( N < numOfElements )
  20. 			N <<= 1;
  21.  
  22. 		cnt = new int [ N << 1 ];
  23. 	}
  24. 	// insert x into the liss of elements ( x is a compressed value )
  25. 	void add(int x)	{
  26. 		x += N;
  27.  
  28. 		if	( x >= cnt.length )
  29. 			throw new IllegalArgumentException("element out of range");
  30.  
  31. 		if	( cnt[x] != 0 )
  32. 			return;		// x is already in set
  33.  
  34. 		while	( x != 0 )	{
  35.  
  36. 			cnt[x]++;
  37.  
  38. 			x >>= 1;
  39. 		}
  40.  
  41. 	}
  42. 	// remove x from the liss of elements (if exists) (x is a compressed value )
  43. 	void remove(int x)	{
  44. 		x += N;
  45.  
  46. 		if	( x >= cnt.length )
  47. 			throw new IllegalArgumentException("element out of range");
  48.  
  49. 		if	( cnt[x] == 0 )
  50. 			return;	// element is not in set
  51.  
  52. 		while	( x != 0 )	{
  53.  
  54. 			cnt[x]--;
  55.  
  56. 			x >>= 1;
  57. 		}
  58.  
  59. 	}
  60.  
  61. 	// find the k-th smallest element from the set, -1 if that element doesn't exists
  62. 	// returns a compressed value
  63. 	int kthSmallestElement(int k)	{
  64.  
  65. 		if	( k > cnt[1] )
  66. 			return	-1;
  67.  
  68. 		int node = 1;
  69. 		while	( node < N )	{
  70.  
  71. 			// is the value in left son?
  72. 			if	( cnt[ node << 1 ] >= k )
  73. 				node <<= 1;
  74. 			else	{
  75. 				// right son
  76. 				node <<= 1;
  77.  
  78. 				k -= cnt[node++];
  79. 			}
  80.  
  81. 		}
  82.  
  83. 		return	node - N;
  84. 	}
  85.  
  86. 	// count how many values are less than x ( x is a compressed value )
  87. 	int count(int x)	{
  88.  
  89. 		int L = N;
  90. 		int R = x - 1 + N;
  91.  
  92. 		int ans = 0;
  93.  
  94. 		while	( L <= R )	{
  95.  
  96. 			if	( L == R )
  97. 				return	ans + cnt[L];
  98.  
  99. 			if ((L & 1) == 1)	ans += cnt[L++];
  100. 			if ((R & 1) == 0)	ans += cnt[R--];
  101.  
  102. 			L >>= 1;
  103. 			R >>= 1;
  104. 		}
  105.  
  106. 		return	ans;
  107. 	}
  108.  
  109. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
Main.java:8: error: class KthElement is public, should be declared in a file named KthElement.java
public class KthElement	{
       ^
1 error
stdout
copy 
Standard output is empty
https://ideone.com/OKpT0o
language:
Java (HotSpot 12)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!