fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define LSOne(S) ((S) & -(S))                    // the key operation
  5.  
  6. typedef long long ll;                            // for extra flexibility
  7. typedef vector<ll> vll;
  8. typedef vector<int> vi;
  9.  
  10. class FenwickTree {                              // index 0 is not used
  11. private:
  12.   vll ft;                                        // internal FT is an array
  13. public:
  14.   FenwickTree(int m) { ft.assign(m+1, 0); }      // create an empty FT
  15.  
  16.   void build(const vll &f) {
  17.     int m = (int)f.size()-1;                     // note f[0] is always 0
  18.     ft.assign(m+1, 0);
  19.     for (int i = 1; i <= m; ++i) {               // O(m)
  20.       ft[i] += f[i];                             // add this value
  21.       if (i+LSOne(i) <= m)                       // i has parent
  22.         ft[i+LSOne(i)] += ft[i];                 // add to that parent
  23.     }
  24.   }
  25.  
  26.   FenwickTree(const vll &f) { build(f); }        // create FT based on f
  27.  
  28.   FenwickTree(int m, const vi &s) {              // create FT based on s
  29.     vll f(m+1, 0);
  30.     for (int i = 0; i < (int)s.size(); ++i)      // do the conversion first
  31.       ++f[s[i]];                                 // in O(n)
  32.     build(f);                                    // in O(m)
  33.   }
  34.  
  35.   ll rsq(int j) {                                // returns RSQ(1, j)
  36.     ll sum = 0;
  37.     for (; j; j -= LSOne(j))
  38.       sum += ft[j];
  39.     return sum;
  40.   }
  41.  
  42.   ll rsq(int i, int j) { return rsq(j) - rsq(i-1); } // inc/exclusion
  43.  
  44.   // updates value of the i-th element by v (v can be +ve/inc or -ve/dec)
  45.   void update(int i, ll v) {
  46.     for (; i < (int)ft.size(); i += LSOne(i))
  47.       ft[i] += v;
  48.   }
  49.  
  50.   int select(ll k) {                             // O(log m)
  51.     int p = 1;
  52.     while (p*2 < (int)ft.size()) p *= 2;
  53.     int i = 0;
  54.     while (p) {
  55.       if (i+p < (int) ft.size() && k > ft[i+p]) {
  56.         k -= ft[i+p];
  57.         i += p;
  58.       }
  59.       p /= 2;
  60.     }
  61.     return i+1;
  62.   }
  63. };
  64.  
  65. int main() {
  66. 	ios_base::sync_with_stdio(false);
  67. 	cin.tie(0);
  68.  
  69. 	for (int size = 1; size <= 10000; size++) {
  70. 		FenwickTree ft(size);
  71. 		for (int i = 1; i <= size; i++) {
  72. 			ft.update(i,1);
  73. 		}
  74. 		for (int i = 1; i <= size; i++) {
  75. 			if (ft.select(i)!=i) {
  76. 				cout << "Failed at size = " << size << " at index = " << i << "\n"; 
  77. 				exit(1);
  78. 			}
  79. 		}
  80. 	}
  81.  
  82. }
  83.  
Success #stdin #stdout 3.48s 4888KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/a8go2h
language:
C++14 (gcc 8.3)
created:
3 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!