fork(1) download
copy 
  1. #include <iostream>
  2. #include <unordered_map>
  3. #include <map>
  4. #include <climits>
  5. using namespace std;
  6. template <class T>
  7. class FenwickTree{
  8. private:
  9.     unordered_map<long long, T> v;
  10.     long long ma;
  11.     long long mi;
  12. public:
  13.     FenwickTree(int max = INT_MAX, int min = 1) : ma(max), mi(min-1L) {}
  14.     void set(long long i, T d){
  15.         if(i<=mi||i>ma) throw "bad_allocation";
  16.         i -= mi;
  17.         while(i<=ma-mi){
  18.             v[i] += d;
  19.             i += i&-i;
  20.         }
  21.     }
  22.     T get(long long i){
  23.         if(i<=mi)   return 0;
  24.         if(i>ma)    i = ma;
  25.         i -= mi;
  26.         T x = NULL;
  27.         while(i){
  28.             x += v[i];
  29.             i -= i&-i;
  30.         }
  31.         return x;
  32.     }
  33. };
  34. class PrefixSum{
  35. private:
  36.     map<int, int> v;
  37. public:
  38.     void set(int i, int d){
  39.     	v[i] += d;
  40.     }
  41.     int get(int i){
  42.     	int x = 0;
  43.     	for(auto p: v)
  44.     		if(p.first>i)	break;
  45.     		else	x += p.second;
  46.     	return x;
  47.     }
  48. };
  49. int main() {
  50. 	int n,q,p;
  51. 	cin>>n>>q>>p;
  52. 	p %= 101;	// p: should be a percentage
  53. 	FenwickTree<int> ft(n,1);
  54. 	PrefixSum ps;
  55. 	int i,d;
  56. 	while(q--){
  57. 		i = 1+rand()%n;
  58. 		d = rand()%100;
  59. 		if(d<p){
  60. 			if(ft.get(i)!=ps.get(i))
  61. 				cout<<"Mismatch at i = "<<i<<" q = "<<q<<endl;
  62. 		}
  63. 		else{
  64. 			d = rand()%100;
  65. 			ft.set(i,d);
  66. 			ps.set(i,d);
  67. 		}
  68. 	}
  69. 	if(ft.get(n)!=ps.get(n))
  70. 		cout<<"Final query mismatch"<<endl;
  71. 	else
  72. 		cout<<"Comparison finished"<<endl;
  73. 	return 0;
  74. }
Success #stdin #stdout 6.89s 4508KB
comments ()
stdin
copy 
10000 1000000 10
stdout
copy 
Comparison finished
https://ideone.com/dIYSUb
Fenwick Tree and its usage for efficient prefix sums
language:
C++14 (gcc 8.3)
created:
4 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!