text:
#include <bits/stdc++.h>
#include "../../../Content/C++/string/LongestCommonPrefix.h"
#include "../../../Content/C++/string/SuffixArray.h"
#include "../../../Content/C++/string/SAISSuffixArray.h"
using namespace std;

void test1() {
  mt19937_64 rng(0);
  int N = 2e6;
  vector<int> A(N);
  for (auto &&ai : A) ai = rng() % int(1e9) + 1;
  const auto start_time = chrono::system_clock::now();
  SuffixArray<int> SA(A);
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 1 (Random, large alphabet, SuffixArray) Passed" << endl;
  cout << "  N: " << N << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  long long checkSum = 0;
  for (auto &&a : SA.ind) checkSum = 31 * checkSum + a;
  for (auto &&a : SA.rnk) checkSum = 31 * checkSum + a;
  for (auto &&a : SA.LCP) checkSum = 31 * checkSum + a;
  cout << "  Checksum: " << checkSum << endl;
}

void test2() {
  mt19937_64 rng(0);
  int N = 2e6;
  vector<int> A(N);
  for (auto &&ai : A) ai = rng() % int(1e9) + 1;
  const auto start_time = chrono::system_clock::now();
  vector<int> tmp = A;
  sort(tmp.begin(), tmp.end());
  tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end());
  for (auto &&ai : A) ai = lower_bound(tmp.begin(), tmp.end(), ai) - tmp.begin();
  SAISSuffixArray<int> SA(A);
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 2 (Random, large alphabet, SAISSuffixArray) Passed" << endl;
  cout << "  N: " << N << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  long long checkSum = 0;
  for (auto &&a : SA.ind) checkSum = 31 * checkSum + a;
  for (auto &&a : SA.rnk) checkSum = 31 * checkSum + a;
  for (auto &&a : SA.LCP) checkSum = 31 * checkSum + a;
  cout << "  Checksum: " << checkSum << endl;
}

void test3() {
  mt19937_64 rng(0);
  int N = 2e6;
  vector<int> A(N);
  for (auto &&ai : A) ai = rng() % N + 1;
  const auto start_time = chrono::system_clock::now();
  SuffixArray<int> SA(A);
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 3 (Random, medium alphabet, SuffixArray) Passed" << endl;
  cout << "  N: " << N << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  long long checkSum = 0;
  for (auto &&a : SA.ind) checkSum = 31 * checkSum + a;
  for (auto &&a : SA.rnk) checkSum = 31 * checkSum + a;
  for (auto &&a : SA.LCP) checkSum = 31 * checkSum + a;
  cout << "  Checksum: " << checkSum << endl;
}

void test4() {
  mt19937_64 rng(0);
  int N = 2e6;
  vector<int> A(N);
  for (auto &&ai : A) ai = rng() % N + 1;
  const auto start_time = chrono::system_clock::now();
  SAISSuffixArray<int> SA(A);
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 4 (Random, medium alphabet, SAISSuffixArray) Passed" << endl;
  cout << "  N: " << N << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  long long checkSum = 0;
  for (auto &&a : SA.ind) checkSum = 31 * checkSum + a;
  for (auto &&a : SA.rnk) checkSum = 31 * checkSum + a;
  for (auto &&a : SA.LCP) checkSum = 31 * checkSum + a;
  cout << "  Checksum: " << checkSum << endl;
}

void test5() {
  mt19937_64 rng(0);
  int N = 2e6;
  vector<int> A(N);
  for (auto &&ai : A) ai = rng() % 26 + 1;
  const auto start_time = chrono::system_clock::now();
  SuffixArray<int> SA(A);
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 5 (Random, small alphabet, SuffixArray) Passed" << endl;
  cout << "  N: " << N << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  long long checkSum = 0;
  for (auto &&a : SA.ind) checkSum = 31 * checkSum + a;
  for (auto &&a : SA.rnk) checkSum = 31 * checkSum + a;
  for (auto &&a : SA.LCP) checkSum = 31 * checkSum + a;
  cout << "  Checksum: " << checkSum << endl;
}

void test6() {
  mt19937_64 rng(0);
  int N = 2e6;
  vector<int> A(N);
  for (auto &&ai : A) ai = rng() % 26 + 1;
  const auto start_time = chrono::system_clock::now();
  SAISSuffixArray<int> SA(A);
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 6 (Random, small alphabet, SAISSuffixArray) Passed" << endl;
  cout << "  N: " << N << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  long long checkSum = 0;
  for (auto &&a : SA.ind) checkSum = 31 * checkSum + a;
  for (auto &&a : SA.rnk) checkSum = 31 * checkSum + a;
  for (auto &&a : SA.LCP) checkSum = 31 * checkSum + a;
  cout << "  Checksum: " << checkSum << endl;
}

void test7() {
  mt19937_64 rng(0);
  int N = 2e6;
  vector<int> B(500);
  for (auto &&bi : B) bi = rng() % N + 1;
  vector<int> A(N);
  for (int i = 0; i < N; i++) A[i] = B[i % 500];
  const auto start_time = chrono::system_clock::now();
  SuffixArray<int> SA(A);
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 7 (Period 500, SuffixArray) Passed" << endl;
  cout << "  N: " << N << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  long long checkSum = 0;
  for (auto &&a : SA.ind) checkSum = 31 * checkSum + a;
  for (auto &&a : SA.rnk) checkSum = 31 * checkSum + a;
  for (auto &&a : SA.LCP) checkSum = 31 * checkSum + a;
  cout << "  Checksum: " << checkSum << endl;
}

void test8() {
  mt19937_64 rng(0);
  int N = 2e6;
  vector<int> B(500);
  for (auto &&bi : B) bi = rng() % N + 1;
  vector<int> A(N);
  for (int i = 0; i < N; i++) A[i] = B[i % 500];
  const auto start_time = chrono::system_clock::now();
  SAISSuffixArray<int> SA(A);
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 8 (Period 500, SAISSuffixArray) Passed" << endl;
  cout << "  N: " << N << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  long long checkSum = 0;
  for (auto &&a : SA.ind) checkSum = 31 * checkSum + a;
  for (auto &&a : SA.rnk) checkSum = 31 * checkSum + a;
  for (auto &&a : SA.LCP) checkSum = 31 * checkSum + a;
  cout << "  Checksum: " << checkSum << endl;
}

void test9() {
  mt19937_64 rng(0);
  int N = 2e6;
  vector<int> A(N, rng() % N + 1);
  const auto start_time = chrono::system_clock::now();
  SuffixArray<int> SA(A);
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 9 (Period 1, SuffixArray) Passed" << endl;
  cout << "  N: " << N << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  long long checkSum = 0;
  for (auto &&a : SA.ind) checkSum = 31 * checkSum + a;
  for (auto &&a : SA.rnk) checkSum = 31 * checkSum + a;
  for (auto &&a : SA.LCP) checkSum = 31 * checkSum + a;
  cout << "  Checksum: " << checkSum << endl;
}

void test10() {
  mt19937_64 rng(0);
  int N = 2e6;
  vector<int> A(N, rng() % N + 1);
  const auto start_time = chrono::system_clock::now();
  SAISSuffixArray<int> SA(A);
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 10 (Period 1, SAISSuffixArray) Passed" << endl;
  cout << "  N: " << N << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  long long checkSum = 0;
  for (auto &&a : SA.ind) checkSum = 31 * checkSum + a;
  for (auto &&a : SA.rnk) checkSum = 31 * checkSum + a;
  for (auto &&a : SA.LCP) checkSum = 31 * checkSum + a;
  cout << "  Checksum: " << checkSum << endl;
}

void test11() {
  mt19937_64 rng(0);
  int N = 2e6;
  vector<int> A(N, rng() % N + 1);
  const auto start_time = chrono::system_clock::now();
  LongestCommonPrefix<SuffixArray<int>> LCP(A);
  int Q = 1e7;
  vector<int> ans;
  for (int i = 0; i < Q; i++) ans.push_back(LCP.lcp(rng() % N, rng() % N));
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 11 (lcp queries, SuffixArray) Passed" << endl;
  cout << "  N: " << N << endl;
  cout << "  Q: " << Q << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  long long checkSum = 0;
  for (auto &&a : ans) checkSum = 31 * checkSum + a;
  cout << "  Checksum: " << checkSum << endl;
}

void test12() {
  mt19937_64 rng(0);
  int N = 2e6;
  vector<int> A(N, rng() % N + 1);
  const auto start_time = chrono::system_clock::now();
  LongestCommonPrefix<SAISSuffixArray<int>> LCP(A);
  int Q = 1e7;
  vector<int> ans;
  for (int i = 0; i < Q; i++) ans.push_back(LCP.lcp(rng() % N, rng() % N));
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 12 (lcp queries, SAISSuffixArray) Passed" << endl;
  cout << "  N: " << N << endl;
  cout << "  Q: " << Q << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  long long checkSum = 0;
  for (auto &&a : ans) checkSum = 31 * checkSum + a;
  cout << "  Checksum: " << checkSum << endl;
}

int main() {
  test1();
  test2();
  test3();
  test4();
  test5();
  test6();
  test7();
  test8();
  test9();
  test10();
  test11();
  test12();
  cout << "Test Passed" << endl;
  return 0;
}


text:
#include <bits/stdc++.h>
#include "../../../Content/C++/datastructures/SparseTable.h"
using namespace std;

void test1() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  const int TESTCASES = 1e5;
  long long checkSum = 0;
  struct Min { int operator () (int a, int b) { return min(a, b); } };
  for (int ti = 0; ti < TESTCASES; ti++) {
    int N = rng() % 101;
    vector<int> A(N);
    for (auto &&a : A) a = rng() % int(1e9) + 1;
    SparseTable<int, Min> ST(A);
    int Q = N == 0 ? 0 : 100 - rng() % 5;
    vector<int> ans0, ans1;
    for (int i = 0; i < Q; i++) {
      int l = rng() % N, r = rng() % N;
      if (l > r) swap(l, r);
      int mn = A[l];
      for (int j = l + 1; j <= r; j++) mn = min(mn, A[j]);
      ans0.push_back(mn);
      ans1.push_back(ST.query(l, r));
    }
    assert(ans0 == ans1);
    for (auto &&a : ans0) checkSum = 31 * checkSum + a;
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 1 Passed" << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  cout << "  Checksum: " << checkSum << endl;
}

int main() {
  test1();
  cout << "Test Passed" << endl;
  return 0;
}

repo_name: wesley-a-leung/Resources

mime_type: text/x-c++


text:
#include <bits/stdc++.h>
#include "../../../Content/C++/datastructures/DisjointSparseTable.h"
using namespace std;

void test1() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  const int TESTCASES = 1e5;
  long long checkSum = 0;
  static constexpr const long long MOD = 1e9;
  struct MulMod { long long operator () (long long a, long long b) { return a * b % MOD; } };
  for (int ti = 0; ti < TESTCASES; ti++) {
    int N = rng() % 101;
    vector<long long> A(N);
    for (auto &&a : A) a = rng() % int(1e9) + 1;
    DisjointSparseTable<long long, MulMod> ST(A);
    int Q = N == 0 ? 0 : 100 - rng() % 5;
    vector<int> ans0, ans1;
    for (int i = 0; i < Q; i++) {
      int l = rng() % N, r = rng() % N;
      if (l > r) swap(l, r);
      long long prod = A[l];
      for (int j = l + 1; j <= r; j++) prod = prod * A[j] % MOD;
      ans0.push_back(prod);
      ans1.push_back(ST.query(l, r));
    }
    assert(ans0 == ans1);
    for (auto &&a : ans0) checkSum = 31 * checkSum + a;
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 1 Passed" << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  cout << "  Checksum: " << checkSum << endl;
}

int main() {
  test1();
  cout << "Test Passed" << endl;
  return 0;
}


text:
#include <bits/stdc++.h>
#include "../../../Content/C++/datastructures/PrefixSumArray2D.h"
using namespace std;

void test1() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  const int TESTCASES = 1e5;
  long long checkSum = 0;
  for (int ti = 0; ti < TESTCASES; ti++) {
    int N = rng() % 11;
    int M = rng() % 21;
    long long A[10][20], B[10][20];
    for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) B[i][j] = A[i][j] = rng() % int(1e6) + 1;
    adjacent_difference_2d(B, N, M, B);
    int U = N == 0 || M == 0 ? 0 : 100 - rng() % 5;
    for (int i = 0; i < U; i++) {
      int u = rng() % N, d = rng() % N, l = rng() % M, r = rng() % M;
      if (u > d) swap(u, d);
      if (l > r) swap(l, r);
      long long v = rng() % int(1e6) + 1;
      add(B, N, M, u, d, l, r, v);
      for (int j = u; j <= d; j++) for (int k = l; k <= r; k++) A[j][k] += v;
    }
    partial_sum_2d(B, N, M, B);
    partial_sum_2d(B, N, M, B);
    int Q = N == 0 || M == 0 ? 0 : 100 - rng() % 5;
    vector<long long> ans0, ans1;
    for (int i = 0; i < Q; i++) {
      int u = rng() % N, d = rng() % N, l = rng() % M, r = rng() % M;
      if (u > d) swap(u, d);
      if (l > r) swap(l, r);
      ans0.push_back(rsq(B, u, d, l, r));
      long long sm = 0;
      for (int j = u; j <= d; j++) for (int k = l; k <= r; k++) sm += A[j][k];
      ans1.push_back(sm);
    }
    assert(ans0 == ans1);
    for (auto &&a : ans0) checkSum = 31 * checkSum + a;
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 1 (C style array) Passed" << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  cout << "  Checksum: " << checkSum << endl;
}

void test2() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  const int TESTCASES = 1e5;
  long long checkSum = 0;
  for (int ti = 0; ti < TESTCASES; ti++) {
    int N = rng() % 11;
    int M = rng() % 21;
    array<array<long long, 20>, 10> A, B;
    for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) B[i][j] = A[i][j] = rng() % int(1e6) + 1;
    adjacent_difference_2d(B, N, M, B);
    int U = N == 0 || M == 0 ? 0 : 100 - rng() % 5;
    for (int i = 0; i < U; i++) {
      int u = rng() % N, d = rng() % N, l = rng() % M, r = rng() % M;
      if (u > d) swap(u, d);
      if (l > r) swap(l, r);
      long long v = rng() % int(1e6) + 1;
      add(B, N, M, u, d, l, r, v);
      for (int j = u; j <= d; j++) for (int k = l; k <= r; k++) A[j][k] += v;
    }
    partial_sum_2d(B, N, M, B);
    partial_sum_2d(B, N, M, B);
    int Q = N == 0 || M == 0 ? 0 : 100 - rng() % 5;
    vector<long long> ans0, ans1;
    for (int i = 0; i < Q; i++) {
      int u = rng() % N, d = rng() % N, l = rng() % M, r = rng() % M;
      if (u > d) swap(u, d);
      if (l > r) swap(l, r);
      ans0.push_back(rsq(B, u, d, l, r));
      long long sm = 0;
      for (int j = u; j <= d; j++) for (int k = l; k <= r; k++) sm += A[j][k];
      ans1.push_back(sm);
    }
    assert(ans0 == ans1);
    for (auto &&a : ans0) checkSum = 31 * checkSum + a;
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 2 (std::array) Passed" << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  cout << "  Checksum: " << checkSum << endl;
}

void test3() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  const int TESTCASES = 1e5;
  long long checkSum = 0;
  for (int ti = 0; ti < TESTCASES; ti++) {
    int N = rng() % 11;
    int M = rng() % 21;
    vector<vector<long long>> A(N, vector<long long>(M)), B(N, vector<long long>(M));
    for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) B[i][j] = A[i][j] = rng() % int(1e6) + 1;
    adjacent_difference_2d(B, N, M, B);
    int U = N == 0 || M == 0 ? 0 : 100 - rng() % 5;
    for (int i = 0; i < U; i++) {
      int u = rng() % N, d = rng() % N, l = rng() % M, r = rng() % M;
      if (u > d) swap(u, d);
      if (l > r) swap(l, r);
      long long v = rng() % int(1e6) + 1;
      add(B, N, M, u, d, l, r, v);
      for (int j = u; j <= d; j++) for (int k = l; k <= r; k++) A[j][k] += v;
    }
    partial_sum_2d(B, N, M, B);
    partial_sum_2d(B, N, M, B);
    int Q = N == 0 || M == 0 ? 0 : 100 - rng() % 5;
    vector<long long> ans0, ans1;
    for (int i = 0; i < Q; i++) {
      int u = rng() % N, d = rng() % N, l = rng() % M, r = rng() % M;
      if (u > d) swap(u, d);
      if (l > r) swap(l, r);
      ans0.push_back(rsq(B, u, d, l, r));
      long long sm = 0;
      for (int j = u; j <= d; j++) for (int k = l; k <= r; k++) sm += A[j][k];
      ans1.push_back(sm);
    }
    assert(ans0 == ans1);
    for (auto &&a : ans0) checkSum = 31 * checkSum + a;
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 3 (std::vector) Passed" << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  cout << "  Checksum: " << checkSum << endl;
}

int main() {
  test1();
  test2();
  test3();
  cout << "Test Passed" << endl;
  return 0;
}


text:
#include <bits/stdc++.h>
#include "../../../Content/C++/datastructures/PrefixSumArray2D.h"
using namespace std;

long long A[4000][6000];
array<array<long long, 6000>, 4000> B;
vector<vector<long long>> C(4000, vector<long long>(6000));

void test1() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  constexpr const int N = 4000;
  constexpr const int M = 6000;
  for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) A[i][j] = rng() % int(1e5) + 1;
  adjacent_difference_2d(A, N, M, A);
  int U = 1;
  for (int i = 0; i < U; i++) {
    int u = rng() % N, d = rng() % N, l = rng() % M, r = rng() % M;
    if (u > d) swap(u, d);
    if (l > r) swap(l, r);
    long long v = rng() % int(1e5) + 1;
    add(A, N, M, u, d, l, r, v);
  }
  partial_sum_2d(A, N, M, A);
  partial_sum_2d(A, N, M, A);
  int Q = 1;
  vector<long long> ans;
  for (int i = 0; i < Q; i++) {
    int u = rng() % N, d = rng() % N, l = rng() % M, r = rng() % M;
    if (u > d) swap(u, d);
    if (l > r) swap(l, r);
    ans.push_back(rsq(A, u, d, l, r));
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 1 (C style array) Passed" << endl;
  cout << "  N: " << N << endl;
  cout << "  M: " << M << endl;
  cout << "  U: " << U << endl;
  cout << "  Q: " << Q << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  long long checkSum = 0;
  for (auto &&a : ans) checkSum = 31 * checkSum + a;
  cout << "  Checksum: " << checkSum << endl;
}

void test2() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  constexpr const int N = 500;
  constexpr const int M = 1000;
  for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) A[i][j] = rng() % int(1e5) + 1;
  adjacent_difference_2d(A, N, M, A);
  int U = 5e6;
  for (int i = 0; i < U; i++) {
    int u = rng() % N, d = rng() % N, l = rng() % M, r = rng() % M;
    if (u > d) swap(u, d);
    if (l > r) swap(l, r);
    long long v = rng() % int(1e5) + 1;
    add(A, N, M, u, d, l, r, v);
  }
  partial_sum_2d(A, N, M, A);
  partial_sum_2d(A, N, M, A);
  int Q = 5e6;
  vector<long long> ans;
  for (int i = 0; i < Q; i++) {
    int u = rng() % N, d = rng() % N, l = rng() % M, r = rng() % M;
    if (u > d) swap(u, d);
    if (l > r) swap(l, r);
    ans.push_back(rsq(A, u, d, l, r));
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 2 (C style array) Passed" << endl;
  cout << "  N: " << N << endl;
  cout << "  M: " << M << endl;
  cout << "  U: " << U << endl;
  cout << "  Q: " << Q << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  long long checkSum = 0;
  for (auto &&a : ans) checkSum = 31 * checkSum + a;
  cout << "  Checksum: " << checkSum << endl;
}

void test3() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  constexpr const int N = 4000;
  constexpr const int M = 6000;
  for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) B[i][j] = rng() % int(1e5) + 1;
  adjacent_difference_2d(B, N, M, B);
  int U = 1;
  for (int i = 0; i < U; i++) {
    int u = rng() % N, d = rng() % N, l = rng() % M, r = rng() % M;
    if (u > d) swap(u, d);
    if (l > r) swap(l, r);
    long long v = rng() % int(1e5) + 1;
    add(B, N, M, u, d, l, r, v);
  }
  partial_sum_2d(B, N, M, B);
  partial_sum_2d(B, N, M, B);
  int Q = 1;
  vector<long long> ans;
  for (int i = 0; i < Q; i++) {
    int u = rng() % N, d = rng() % N, l = rng() % M, r = rng() % M;
    if (u > d) swap(u, d);
    if (l > r) swap(l, r);
    ans.push_back(rsq(B, u, d, l, r));
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 3 (std::array) Passed" << endl;
  cout << "  N: " << N << endl;
  cout << "  M: " << M << endl;
  cout << "  U: " << U << endl;
  cout << "  Q: " << Q << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  long long checkSum = 0;
  for (auto &&a : ans) checkSum = 31 * checkSum + a;
  cout << "  Checksum: " << checkSum << endl;
}

void test4() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  constexpr const int N = 500;
  constexpr const int M = 1000;
  for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) B[i][j] = rng() % int(1e5) + 1;
  adjacent_difference_2d(B, N, M, B);
  int U = 5e6;
  for (int i = 0; i < U; i++) {
    int u = rng() % N, d = rng() % N, l = rng() % M, r = rng() % M;
    if (u > d) swap(u, d);
    if (l > r) swap(l, r);
    long long v = rng() % int(1e5) + 1;
    add(B, N, M, u, d, l, r, v);
  }
  partial_sum_2d(B, N, M, B);
  partial_sum_2d(B, N, M, B);
  int Q = 5e6;
  vector<long long> ans;
  for (int i = 0; i < Q; i++) {
    int u = rng() % N, d = rng() % N, l = rng() % M, r = rng() % M;
    if (u > d) swap(u, d);
    if (l > r) swap(l, r);
    ans.push_back(rsq(B, u, d, l, r));
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 4 (std::array) Passed" << endl;
  cout << "  N: " << N << endl;
  cout << "  M: " << M << endl;
  cout << "  U: " << U << endl;
  cout << "  Q: " << Q << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  long long checkSum = 0;
  for (auto &&a : ans) checkSum = 31 * checkSum + a;
  cout << "  Checksum: " << checkSum << endl;
}

void test5() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  constexpr const int N = 4000;
  constexpr const int M = 6000;
  for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) C[i][j] = rng() % int(1e5) + 1;
  adjacent_difference_2d(C, N, M, C);
  int U = 1;
  for (int i = 0; i < U; i++) {
    int u = rng() % N, d = rng() % N, l = rng() % M, r = rng() % M;
    if (u > d) swap(u, d);
    if (l > r) swap(l, r);
    long long v = rng() % int(1e5) + 1;
    add(C, N, M, u, d, l, r, v);
  }
  partial_sum_2d(C, N, M, C);
  partial_sum_2d(C, N, M, C);
  int Q = 1;
  vector<long long> ans;
  for (int i = 0; i < Q; i++) {
    int u = rng() % N, d = rng() % N, l = rng() % M, r = rng() % M;
    if (u > d) swap(u, d);
    if (l > r) swap(l, r);
    ans.push_back(rsq(C, u, d, l, r));
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 5 (std::vector) Passed" << endl;
  cout << "  N: " << N << endl;
  cout << "  M: " << M << endl;
  cout << "  U: " << U << endl;
  cout << "  Q: " << Q << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  long long checkSum = 0;
  for (auto &&a : ans) checkSum = 31 * checkSum + a;
  cout << "  Checksum: " << checkSum << endl;
}

void test6() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  constexpr const int N = 500;
  constexpr const int M = 1000;
  for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) C[i][j] = rng() % int(1e5) + 1;
  adjacent_difference_2d(C, N, M, C);
  int U = 5e6;
  for (int i = 0; i < U; i++) {
    int u = rng() % N, d = rng() % N, l = rng() % M, r = rng() % M;
    if (u > d) swap(u, d);
    if (l > r) swap(l, r);
    long long v = rng() % int(1e5) + 1;
    add(C, N, M, u, d, l, r, v);
  }
  partial_sum_2d(C, N, M, C);
  partial_sum_2d(C, N, M, C);
  int Q = 5e6;
  vector<long long> ans;
  for (int i = 0; i < Q; i++) {
    int u = rng() % N, d = rng() % N, l = rng() % M, r = rng() % M;
    if (u > d) swap(u, d);
    if (l > r) swap(l, r);
    ans.push_back(rsq(C, u, d, l, r));
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 6 (std::vector) Passed" << endl;
  cout << "  N: " << N << endl;
  cout << "  M: " << M << endl;
  cout << "  U: " << U << endl;
  cout << "  Q: " << Q << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  long long checkSum = 0;
  for (auto &&a : ans) checkSum = 31 * checkSum + a;
  cout << "  Checksum: " << checkSum << endl;
}

int main() {
  test1();
  test2();
  test3();
  test4();
  test5();
  test6();
  cout << "Test Passed" << endl;
  return 0;
}


text:
#include <bits/stdc++.h>
#include "../../../Content/C++/datastructures/WaveletMatrixAggregation.h"
#include "../../../Content/C++/datastructures/trees/fenwicktrees/BitFenwickTree.h"
using namespace std;

struct R {
  using Data = int;
  using Lazy = int;
  static Data qdef() { return 0; }
  static Data merge(const Data &l, const Data &r) { return l + r; }
  BitFenwickTree FT;
  R(const vector<Data> &A) : FT(A.size()) {
    for (int i = 0; i < int(A.size()); i++) FT.set(i, A[i]);
    FT.build();
  }
  void update(int i, const Lazy &val) { FT.update(i, val); }
  Data query(int l, int r) { return FT.query(l, r); }
};

void test1() {
  mt19937_64 rng(0);
  constexpr const int N = 1e6, Q = 1e6, MAXA = 1e9;
  long long checkSum = 0;
  vector<int> A(N, 0);
  for (int i = 0; i < N; i++) A[i] = rng() % MAXA;
  vector<int> B(N, 0);
  for (int i = 0; i < N; i++) B[i] = rng() % 2;
  const auto start_time = chrono::system_clock::now();
  WaveletMatrixAggregation<int, R> wm(A, B);
  vector<int> ans;
  ans.reserve(Q);
  for (int i = 0; i < Q; i++) {
    int t = rng() % 3;
    if (t == 0) {
      int j = rng() % N;
      wm.update(j, B[j] ^= 1);
    } else if (t == 1) {
      int l = rng() % N, r = rng() % N, a = rng() % MAXA, b = rng() % MAXA;
      if (l > r) swap(l, r);
      if (a > b) swap(a, b);
      ans.push_back(wm.query(l, r, a, b));
    } else {
      int l = rng() % N, r = rng() % N;
      if (l > r) swap(l, r);
      int k = rng() % ((wm.query(l, r, MAXA) + 1) * 2);
      pair<bool, int *> p = wm.bsearch(l, r, [&] (int agg) {
        return agg >= k;
      });
      ans.push_back(p.first ? *p.second : INT_MAX);
    }
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 1 Passed" << endl;
  cout << "  N: " << N << endl;
  cout << "  Q: " << Q << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  for (auto &&a : ans) checkSum = 31 * checkSum + a;
  cout << "  Checksum: " << checkSum << endl;
}

int main() {
  test1();
  cout << "Test Passed" << endl;
  return 0;
}


text:
#include <bits/stdc++.h>
#include "../../../Content/C++/datastructures/DisjointSparseTable.h"
#include "../../../Content/C++/datastructures/FischerHeunStructure.h"
#include "../../../Content/C++/datastructures/SparseTable.h"
#include "../../../Content/C++/datastructures/trees/segmenttrees/SegmentTreeBottomUp.h"
using namespace std;

void test1() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  struct Min { int operator () (int a, int b) { return min(a, b); } };
  int N = 2e6;
  vector<int> A(N);
  for (auto &&ai : A) ai = rng() % int(1e9) + 1;
  SparseTable<int, Min> ST(A);
  int Q = 1;
  vector<int> ans;
  ans.reserve(Q);
  for (int i = 0; i < Q; i++) {
    int l = rng() % N, r = rng() % N;
    if (l > r) swap(l, r);
    ans.push_back(ST.query(l, r));
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 1 (Sparse Table) Passed" << endl;
  cout << "  N: " << N << endl;
  cout << "  Q: " << Q << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  long long checkSum = 0;
  for (auto &&a : ans) checkSum = 31 * checkSum + a;
  cout << "  Checksum: " << checkSum << endl;
}

void test2() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  struct Min { int operator () (int a, int b) { return min(a, b); } };
  int N = 2e6;
  vector<int> A(N);
  for (auto &&ai : A) ai = rng() % int(1e9) + 1;
  SparseTable<int, Min> ST(A);
  int Q = 1e7;
  vector<int> ans;
  ans.reserve(Q);
  for (int i = 0; i < Q; i++) {
    int l = rng() % N, r = rng() % N;
    if (l > r) swap(l, r);
    ans.push_back(ST.query(l, r));
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 2 (Sparse Table) Passed" << endl;
  cout << "  N: " << N << endl;
  cout << "  Q: " << Q << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  long long checkSum = 0;
  for (auto &&a : ans) checkSum = 31 * checkSum + a;
  cout << "  Checksum: " << checkSum << endl;
}

void test3() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  struct Min { int operator () (int a, int b) { return min(a, b); } };
  int N = 2e6;
  vector<int> A(N);
  for (auto &&ai : A) ai = rng() % int(1e9) + 1;
  DisjointSparseTable<int, Min> ST(A);
  int Q = 1;
  vector<int> ans;
  ans.reserve(Q);
  for (int i = 0; i < Q; i++) {
    int l = rng() % N, r = rng() % N;
    if (l > r) swap(l, r);
    ans.push_back(ST.query(l, r));
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 3 (Disjoint Sparse Table) Passed" << endl;
  cout << "  N: " << N << endl;
  cout << "  Q: " << Q << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  long long checkSum = 0;
  for (auto &&a : ans) checkSum = 31 * checkSum + a;
  cout << "  Checksum: " << checkSum << endl;
}

void test4() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  struct Min { int operator () (int a, int b) { return min(a, b); } };
  int N = 2e6;
  vector<int> A(N);
  for (auto &&ai : A) ai = rng() % int(1e9) + 1;
  DisjointSparseTable<int, Min> ST(A);
  int Q = 1e7;
  vector<int> ans;
  ans.reserve(Q);
  for (int i = 0; i < Q; i++) {
    int l = rng() % N, r = rng() % N;
    if (l > r) swap(l, r);
    ans.push_back(ST.query(l, r));
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 4 (Disjoint Sparse Table) Passed" << endl;
  cout << "  N: " << N << endl;
  cout << "  Q: " << Q << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  long long checkSum = 0;
  for (auto &&a : ans) checkSum = 31 * checkSum + a;
  cout << "  Checksum: " << checkSum << endl;
}

void test5() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  int N = 2e6;
  vector<int> A(N);
  for (auto &&ai : A) ai = rng() % int(1e9) + 1;
  FischerHeunStructure<int, greater<int>> ST(A);
  int Q = 1;
  vector<int> ans;
  ans.reserve(Q);
  for (int i = 0; i < Q; i++) {
    int l = rng() % N, r = rng() % N;
    if (l > r) swap(l, r);
    ans.push_back(ST.query(l, r));
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 5 (Fischer Heun) Passed" << endl;
  cout << "  N: " << N << endl;
  cout << "  Q: " << Q << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  long long checkSum = 0;
  for (auto &&a : ans) checkSum = 31 * checkSum + a;
  cout << "  Checksum: " << checkSum << endl;
}

void test6() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  int N = 2e6;
  vector<int> A(N);
  for (auto &&ai : A) ai = rng() % int(1e9) + 1;
  FischerHeunStructure<int, greater<int>> ST(A);
  int Q = 1e7;
  vector<int> ans;
  ans.reserve(Q);
  for (int i = 0; i < Q; i++) {
    int l = rng() % N, r = rng() % N;
    if (l > r) swap(l, r);
    ans.push_back(ST.query(l, r));
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 6 (Fischer Heun) Passed" << endl;
  cout << "  N: " << N << endl;
  cout << "  Q: " << Q << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  long long checkSum = 0;
  for (auto &&a : ans) checkSum = 31 * checkSum + a;
  cout << "  Checksum: " << checkSum << endl;
}

void test7() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  int N = 2e6;
  vector<int> A(N);
  for (auto &&ai : A) ai = rng() % int(1e9) + 1;
  struct Combine {
    using Data = int;
    using Lazy = int;
    static Data qdef() { return numeric_limits<int>::max(); }
    static Data merge(const Data &l, const Data &r) { return min(l, r); }
  };
  SegmentTreeBottomUp<Combine> ST(A);
  int Q = 1;
  vector<int> ans;
  ans.reserve(Q);
  for (int i = 0; i < Q; i++) {
    int l = rng() % N, r = rng() % N;
    if (l > r) swap(l, r);
    ans.push_back(ST.query(l, r));
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 7 (Segment Tree) Passed" << endl;
  cout << "  N: " << N << endl;
  cout << "  Q: " << Q << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  long long checkSum = 0;
  for (auto &&a : ans) checkSum = 31 * checkSum + a;
  cout << "  Checksum: " << checkSum << endl;
}

void test8() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  int N = 2e6;
  vector<int> A(N);
  for (auto &&ai : A) ai = rng() % int(1e9) + 1;
  struct Combine {
    using Data = int;
    using Lazy = int;
    static Data qdef() { return numeric_limits<int>::max(); }
    static Data merge(const Data &l, const Data &r) { return min(l, r); }
  };
  SegmentTreeBottomUp<Combine> ST(A);
  int Q = 1e7;
  vector<int> ans;
  ans.reserve(Q);
  for (int i = 0; i < Q; i++) {
    int l = rng() % N, r = rng() % N;
    if (l > r) swap(l, r);
    ans.push_back(ST.query(l, r));
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 8 (Segment Tree) Passed" << endl;
  cout << "  N: " << N << endl;
  cout << "  Q: " << Q << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  long long checkSum = 0;
  for (auto &&a : ans) checkSum = 31 * checkSum + a;
  cout << "  Checksum: " << checkSum << endl;
}

int main() {
  test1();
  test2();
  test3();
  test4();
  test5();
  test6();
  test7();
  test8();
  cout << "Test Passed" << endl;
  return 0;
}


text:
#include <bits/stdc++.h>
#include "../../../Content/C++/datastructures/WaveletMatrixAggregation.h"
#include "../../../Content/C++/datastructures/trees/fenwicktrees/BitFenwickTree.h"
using namespace std;

struct R {
  using Data = int;
  using Lazy = int;
  static Data qdef() { return 0; }
  static Data merge(const Data &l, const Data &r) { return l + r; }
  BitFenwickTree FT;
  R(const vector<Data> &A) : FT(A.size()) {
    for (int i = 0; i < int(A.size()); i++) FT.set(i, A[i]);
    FT.build();
  }
  void update(int i, const Lazy &val) { FT.update(i, val); }
  Data query(int l, int r) { return FT.query(l, r); }
};

void test1() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  const int TESTCASES = 1e5, MAXA = 100;
  long long checkSum = 0;
  for (int ti = 0; ti < TESTCASES; ti++) {
    int N = rng() % 101;
    vector<int> A(N, 0);
    for (int i = 0; i < N; i++) A[i] = rng() % MAXA;
    vector<int> B(N, 0);
    for (int i = 0; i < N; i++) B[i] = rng() % 2;
    WaveletMatrixAggregation<int, R> wm(A, B);
    int Q = N == 0 ? 0 : rng() % 101;
    vector<int> ans0, ans1;
    for (int i = 0; i < Q; i++) {
      int t = rng() % 3;
      if (t == 0) {
        int j = rng() % N;
        wm.update(j, B[j] ^= 1);
      } else if (t == 1) {
        int l = rng() % N, r = rng() % N, a = rng() % MAXA, b = rng() % MAXA;
        if (l > r) swap(l, r);
        if (a > b) swap(a, b);
        int sm = 0;
        for (int j = l; j <= r; j++) if (a <= A[j] && A[j] <= b) sm += B[j];
        ans0.push_back(sm);
        ans1.push_back(wm.query(l, r, a, b));
      } else {
        int l = rng() % N, r = rng() % N;
        if (l > r) swap(l, r);
        int k = rng() % ((wm.query(l, r, MAXA) + 1) * 2);
        vector<int> C;
        for (int j = l; j <= r; j++) if (B[j]) C.push_back(A[j]);
        sort(C.begin(), C.end());
        if (k == 0) ans0.push_back(*min_element(A.begin(), A.end()));
        else if (k - 1 < int(C.size())) ans0.push_back(C[k - 1]);
        else ans0.push_back(INT_MAX);
        pair<bool, int *> p = wm.bsearch(l, r, [&] (int agg) {
          return agg >= k;
        });
        ans1.push_back(p.first ? *p.second : INT_MAX);
      }
    }
    assert(ans0 == ans1);
    for (auto &&a : ans0) checkSum = 31 * checkSum + a;
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 1 Passed" << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  cout << "  Checksum: " << checkSum << endl;
}

int main() {
  test1();
  cout << "Test Passed" << endl;
  return 0;
}


text:
#include <bits/stdc++.h>
#include "../../../Content/C++/datastructures/SparseTable2D.h"
#include "../../../Content/C++/datastructures/FischerHeunStructure2D.h"
#include "../../../Content/C++/datastructures/trees/segmenttrees/SegmentTreeBottomUp2D.h"
using namespace std;

void test1() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  struct Min { int operator () (int a, int b) { return min(a, b); } };
  int N = 500, M = 1000;
  vector<vector<int>> A(N, vector<int>(M));
  for (auto &&ai : A) for (auto &&aij : ai) aij = rng() % int(1e9) + 1;
  SparseTable2D<int, Min> ST(A);
  int Q = 1;
  vector<int> ans;
  for (int i = 0; i < Q; i++) {
    int u = rng() % N, d = rng() % N, l = rng() % M, r = rng() % M;
    if (u > d) swap(u, d);
    if (l > r) swap(l, r);
    ans.push_back(ST.query(u, d, l, r));
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 1 (Sparse Table) Passed" << endl;
  cout << "  N: " << N << endl;
  cout << "  M: " << M << endl;
  cout << "  Q: " << Q << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  long long checkSum = 0;
  for (auto &&a : ans) checkSum = 31 * checkSum + a;
  cout << "  Checksum: " << checkSum << endl;
}

void test2() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  struct Min { int operator () (int a, int b) { return min(a, b); } };
  int N = 500, M = 1000;
  vector<vector<int>> A(N, vector<int>(M));
  for (auto &&ai : A) for (auto &&aij : ai) aij = rng() % int(1e9) + 1;
  SparseTable2D<int, Min> ST(A);
  int Q = 1e7;
  vector<int> ans;
  for (int i = 0; i < Q; i++) {
    int u = rng() % N, d = rng() % N, l = rng() % M, r = rng() % M;
    if (u > d) swap(u, d);
    if (l > r) swap(l, r);
    ans.push_back(ST.query(u, d, l, r));
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 2 (Sparse Table) Passed" << endl;
  cout << "  N: " << N << endl;
  cout << "  M: " << M << endl;
  cout << "  Q: " << Q << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  long long checkSum = 0;
  for (auto &&a : ans) checkSum = 31 * checkSum + a;
  cout << "  Checksum: " << checkSum << endl;
}

void test3() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  int N = 500, M = 1000;
  vector<vector<int>> A(N, vector<int>(M));
  for (auto &&ai : A) for (auto &&aij : ai) aij = rng() % int(1e9) + 1;
  FischerHeunStructure2D<int, greater<int>> FHS(A);
  int Q = 1;
  vector<int> ans;
  for (int i = 0; i < Q; i++) {
    int u = rng() % N, d = rng() % N, l = rng() % M, r = rng() % M;
    if (u > d) swap(u, d);
    if (l > r) swap(l, r);
    ans.push_back(FHS.query(u, d, l, r));
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 3 (Fischer Heun Structure) Passed" << endl;
  cout << "  N: " << N << endl;
  cout << "  M: " << M << endl;
  cout << "  Q: " << Q << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  long long checkSum = 0;
  for (auto &&a : ans) checkSum = 31 * checkSum + a;
  cout << "  Checksum: " << checkSum << endl;
}

void test4() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  int N = 500, M = 1000;
  vector<vector<int>> A(N, vector<int>(M));
  for (auto &&ai : A) for (auto &&aij : ai) aij = rng() % int(1e9) + 1;
  FischerHeunStructure2D<int, greater<int>> FHS(A);
  int Q = 1e7;
  vector<int> ans;
  for (int i = 0; i < Q; i++) {
    int u = rng() % N, d = rng() % N, l = rng() % M, r = rng() % M;
    if (u > d) swap(u, d);
    if (l > r) swap(l, r);
    ans.push_back(FHS.query(u, d, l, r));
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 4 (Fischer Heun Structure) Passed" << endl;
  cout << "  N: " << N << endl;
  cout << "  M: " << M << endl;
  cout << "  Q: " << Q << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  long long checkSum = 0;
  for (auto &&a : ans) checkSum = 31 * checkSum + a;
  cout << "  Checksum: " << checkSum << endl;
}

struct C {
  using Data = int;
  using Lazy = int;
  static Data qdef() { return numeric_limits<int>::max(); }
  static Data merge(const Data &l, const Data &r) {
    return min(l, r);
  }
  static Data applyLazy(const Data &, const Lazy &r) {
    return r;
  }
};

void test5() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  int N = 500, M = 1000;
  vector<vector<int>> A(N, vector<int>(M));
  for (auto &&ai : A) for (auto &&aij : ai) aij = rng() % int(1e9) + 1;
  SegmentTreeBottomUp2D<C> ST(A);
  int Q = 1;
  vector<int> ans;
  for (int i = 0; i < Q; i++) {
    int u = rng() % N, d = rng() % N, l = rng() % M, r = rng() % M;
    if (u > d) swap(u, d);
    if (l > r) swap(l, r);
    ans.push_back(ST.query(u, d, l, r));
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 5 (Segment Tree) Passed" << endl;
  cout << "  N: " << N << endl;
  cout << "  M: " << M << endl;
  cout << "  Q: " << Q << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  long long checkSum = 0;
  for (auto &&a : ans) checkSum = 31 * checkSum + a;
  cout << "  Checksum: " << checkSum << endl;
}

void test6() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  int N = 500, M = 1000;
  vector<vector<int>> A(N, vector<int>(M));
  for (auto &&ai : A) for (auto &&aij : ai) aij = rng() % int(1e9) + 1;
  SegmentTreeBottomUp2D<C> ST(A);
  int Q = 1e7;
  vector<int> ans;
  for (int i = 0; i < Q; i++) {
    int u = rng() % N, d = rng() % N, l = rng() % M, r = rng() % M;
    if (u > d) swap(u, d);
    if (l > r) swap(l, r);
    ans.push_back(ST.query(u, d, l, r));
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 6 (Segment Tree) Passed" << endl;
  cout << "  N: " << N << endl;
  cout << "  M: " << M << endl;
  cout << "  Q: " << Q << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  long long checkSum = 0;
  for (auto &&a : ans) checkSum = 31 * checkSum + a;
  cout << "  Checksum: " << checkSum << endl;
}

int main() {
  test1();
  test2();
  test3();
  test4();
  test5();
  test6();
  cout << "Test Passed" << endl;
  return 0;
}


text:
#include <bits/stdc++.h>
#include "../../../Content/C++/datastructures/BitPrefixSumArray.h"
using namespace std;

void test1() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  const int TESTCASES = 5e4;
  long long checkSum = 0;
  for (int ti = 0; ti < TESTCASES; ti++) {
    int N = rng() % 1001;
    vector<int> A(N + 1, 0);
    BitPrefixSumArray bpsa(N);
    int U = N == 0 ? 0 : 1000 - rng() % 5;
    for (int i = 0; i < U; i++) {
      int j = rng() % N, v = rng() % 2;
      A[j + 1] = v;
      bpsa.set(j, v);
    }
    for (int i = 0; i < N; i++) assert(A[i + 1] == bpsa.get(i));
    partial_sum(A.begin(), A.end(), A.begin());
    bpsa.build();
    int Q = N == 0 ? 0 : 1000 - rng() % 5;
    vector<int> ans0, ans1;
    for (int i = 0; i < Q; i++) {
      int l = rng() % N, r = rng() % N;
      if (l > r) swap(l, r);
      ans0.push_back(A[r + 1] - A[l]);
      ans1.push_back(bpsa.query(l, r));
    }
    assert(ans0 == ans1);
    for (auto &&a : ans0) checkSum = 31 * checkSum + a;
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 1 Passed" << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  cout << "  Checksum: " << checkSum << endl;
}

int main() {
  test1();
  cout << "Test Passed" << endl;
  return 0;
}


text:
#include <bits/stdc++.h>
#include "../../../Content/C++/datastructures/SparseTable2D.h"
#include "../../../Content/C++/datastructures/FischerHeunStructure2D.h"
using namespace std;

void test1() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  const int TESTCASES = 1e5;
  long long checkSum = 0;
  struct Min { int operator () (int a, int b) { return min(a, b); } };
  for (int ti = 0; ti < TESTCASES; ti++) {
    int N = rng() % 11;
    int M = rng() % 21;
    vector<vector<int>> A(N, vector<int>(M));
    for (auto &&ai : A) for (auto &&aij : ai) aij = rng() % int(1e9) + 1;
    SparseTable2D<int, Min> ST(A);
    int Q = N == 0 || M == 0 ? 0 : 100 - rng() % 5;
    vector<int> ans0, ans1;
    for (int i = 0; i < Q; i++) {
      int u = rng() % N, d = rng() % N, l = rng() % M, r = rng() % M;
      if (u > d) swap(u, d);
      if (l > r) swap(l, r);
      int mn = A[u][l];
      for (int j = u; j <= d; j++) for (int k = l; k <= r; k++) mn = min(mn, A[j][k]);
      ans0.push_back(mn);
      ans1.push_back(ST.query(u, d, l, r));
    }
    assert(ans0 == ans1);
    for (auto &&a : ans0) checkSum = 31 * checkSum + a;
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 1 (Sparse Table) Passed" << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  cout << "  Checksum: " << checkSum << endl;
}

void test2() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  const int TESTCASES = 1e5;
  long long checkSum = 0;
  for (int ti = 0; ti < TESTCASES; ti++) {
    int N = rng() % 11;
    int M = rng() % 21;
    vector<vector<int>> A(N, vector<int>(M));
    for (auto &&ai : A) for (auto &&aij : ai) aij = rng() % int(1e9) + 1;
    FischerHeunStructure2D<int, greater<int>> FHS(A);
    int Q = N == 0 || M == 0 ? 0 : 100 - rng() % 5;
    vector<int> ans0, ans1;
    for (int i = 0; i < Q; i++) {
      int u = rng() % N, d = rng() % N, l = rng() % M, r = rng() % M;
      if (u > d) swap(u, d);
      if (l > r) swap(l, r);
      int mn = A[u][l];
      for (int j = u; j <= d; j++) for (int k = l; k <= r; k++) mn = min(mn, A[j][k]);
      ans0.push_back(mn);
      ans1.push_back(FHS.query(u, d, l, r));
    }
    assert(ans0 == ans1);
    for (auto &&a : ans0) checkSum = 31 * checkSum + a;
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 2 (Fischer Heun Structure) Passed" << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  cout << "  Checksum: " << checkSum << endl;
}

int main() {
  test1();
  test2();
  cout << "Test Passed" << endl;
  return 0;
}


text:
#include <bits/stdc++.h>
#include "../../../Content/C++/datastructures/BitPrefixSumArray.h"
using namespace std;

void test1() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  constexpr const int N = 1e7, U = 1e7, Q = 1e7;
  vector<int> A(N + 1);
  for (int i = 0; i < U; i++) {
    int j = rng() % N, v = rng() % 2;
    A[j + 1] = v;
  }
  partial_sum(A.begin(), A.end(), A.begin());
  vector<int> ans;
  ans.reserve(Q);
  for (int i = 0; i < Q; i++) {
    int l = rng() % N, r = rng() % N;
    if (l > r) swap(l, r);
    ans.push_back(A[r + 1] - A[l]);
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 1 (Prefix Sum) Passed" << endl;
  cout << "  N: " << N << endl;
  cout << "  U: " << U << endl;
  cout << "  Q: " << Q << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  long long checkSum = 0;
  for (auto &&a : ans) checkSum = 31 * checkSum + a;
  cout << "  Checksum: " << checkSum << endl;
}

void test2() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  constexpr const int N = 1e7, U = 1e7, Q = 1e7;
  BitPrefixSumArray bpsa(N);
  for (int i = 0; i < U; i++) {
    int j = rng() % N, v = rng() % 2;
    bpsa.set(j, v);
  }
  bpsa.build();
  vector<int> ans;
  ans.reserve(Q);
  for (int i = 0; i < Q; i++) {
    int l = rng() % N, r = rng() % N;
    if (l > r) swap(l, r);
    ans.push_back(bpsa.query(l, r));
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 2 (Bit Prefix Sum) Passed" << endl;
  cout << "  N: " << N << endl;
  cout << "  U: " << U << endl;
  cout << "  Q: " << Q << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  long long checkSum = 0;
  for (auto &&a : ans) checkSum = 31 * checkSum + a;
  cout << "  Checksum: " << checkSum << endl;
}

void test3() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  constexpr const int N = 1e9, U = 1e7, Q = 1e7;
  BitPrefixSumArray bpsa(N);
  for (int i = 0; i < U; i++) {
    int j = rng() % N, v = rng() % 2;
    bpsa.set(j, v);
  }
  bpsa.build();
  vector<int> ans;
  ans.reserve(Q);
  for (int i = 0; i < Q; i++) {
    int l = rng() % N, r = rng() % N;
    if (l > r) swap(l, r);
    ans.push_back(bpsa.query(l, r));
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 3 (Bit Prefix Sum) Passed" << endl;
  cout << "  N: " << N << endl;
  cout << "  U: " << U << endl;
  cout << "  Q: " << Q << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  long long checkSum = 0;
  for (auto &&a : ans) checkSum = 31 * checkSum + a;
  cout << "  Checksum: " << checkSum << endl;
}

int main() {
  test1();
  test2();
  test3();
  cout << "Test Passed" << endl;
  return 0;
}


text:
#include <bits/stdc++.h>
#include "../../../Content/C++/datastructures/FischerHeunStructure.h"
using namespace std;

void test1() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  const int TESTCASES = 1e5;
  long long checkSum = 0;
  for (int ti = 0; ti < TESTCASES; ti++) {
    int N = rng() % 101;
    vector<int> A(N);
    for (auto &&a : A) a = rng() % int(100) + 1;
    FischerHeunStructure<int, greater<int>> FHS(A);
    int Q = N == 0 ? 0 : 100 - rng() % 5;
    vector<int> ans0, ans1, ansA0, ansA1;
    for (int i = 0; i < Q; i++) {
      int l = rng() % N, r = rng() % N;
      if (l > r) swap(l, r);
      int mnInd = l;
      for (int j = l + 1; j <= r; j++) if (A[mnInd] > A[j]) mnInd = j;
      ans0.push_back(mnInd);
      ansA0.push_back(A[ans0.back()]);
      ans1.push_back(FHS.queryInd(l, r));
      ansA1.push_back(A[ans1.back()]);
    }
    assert(ans0 == ans1);
    assert(ansA0 == ansA1);
    for (auto &&a : ans0) checkSum = 31 * checkSum + a;
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 1 Passed" << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  cout << "  Checksum: " << checkSum << endl;
}

void test2() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  const int TESTCASES = 1e5;
  long long checkSum = 0;
  for (int ti = 0; ti < TESTCASES; ti++) {
    int N = rng() % 101;
    vector<int> A(N);
    for (auto &&a : A) a = rng() % int(100) + 1;
    FischerHeunStructure<int, greater_equal<int>> FHS(A);
    int Q = N == 0 ? 0 : 100 - rng() % 5;
    vector<int> ans0, ans1, ansA0, ansA1;
    for (int i = 0; i < Q; i++) {
      int l = rng() % N, r = rng() % N;
      if (l > r) swap(l, r);
      int mnInd = l;
      for (int j = l + 1; j <= r; j++) if (A[mnInd] >= A[j]) mnInd = j;
      ans0.push_back(mnInd);
      ansA0.push_back(A[ans0.back()]);
      ans1.push_back(FHS.queryInd(l, r));
      ansA1.push_back(A[ans1.back()]);
    }
    assert(ans0 == ans1);
    assert(ansA0 == ansA1);
    for (auto &&a : ans0) checkSum = 31 * checkSum + a;
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 2 Passed" << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  cout << "  Checksum: " << checkSum << endl;
}

int main() {
  test1();
  test2();
  cout << "Test Passed" << endl;
  return 0;
}


text:
#include <bits/stdc++.h>
#include "../../../../Content/C++/datastructures/unionfind/UnionFind.h"
using namespace std;

void test1() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  const int TESTCASES = 1e5;
  long long checkSum = 0;
  for (int ti = 0; ti < TESTCASES; ti++) {
    int N = rng() % 101;
    UnionFind uf(N);
    vector<vector<int>> sets(N);
    vector<int> par(N);
    for (int i = 0; i < N; i++) sets[par[i] = i].push_back(i);
    int Q = N == 0 ? 0 : 100 - rng() % 5;
    vector<int> ans0, ans1;
    for (int i = 0; i < Q; i++) {
      if (rng() % 2 == 0) {
        int v = rng() % N;
        ans0.push_back(int(sets[par[v]].size()));
        ans1.push_back(uf.getSize(v));
      } else {
        int v = rng() % N, w = rng() % N;
        if (sets[par[v]].size() < sets[par[w]].size()) swap(v, w);
        if (par[w] != par[v]) for (int x : sets[par[w]]) sets[par[x] = par[v]].push_back(x);
        uf.join(v, w);
      }
    }
    assert(ans0 == ans1);
    for (auto &&a : ans0) checkSum = 31 * checkSum + a;
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 1 Passed" << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  cout << "  Checksum: " << checkSum << endl;
}

int main() {
  test1();
  cout << "Test Passed" << endl;
  return 0;
}


text:
#include <bits/stdc++.h>
#include "../../../../Content/C++/datastructures/unionfind/UnionFind.h"
using namespace std;

void test1() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  int N = 2e6;
  UnionFind uf(N);
  int Q = 1e7;
  vector<int> ans;
  for (int i = 0; i < Q; i++) {
    if (rng() % 2 == 0) ans.push_back(uf.getSize(rng() % N));
    else {
      int v = rng() % N, w = rng() % N;
      uf.join(v, w);
    }
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 1 Passed" << endl;
  cout << "  N: " << N << endl;
  cout << "  Q: " << Q << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  long long checkSum = 0;
  for (auto &&a : ans) checkSum = 31 * checkSum + a;
  cout << "  Checksum: " << checkSum << endl;
}

int main() {
  test1();
  cout << "Test Passed" << endl;
  return 0;
}


text:
#include <bits/stdc++.h>
#include "../../../../Content/C++/datastructures/trees/BinaryTrie.h"
using namespace std;

void test1() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  const int TESTCASES = 5e4;
  long long checkSum = 0;
  for (int ti = 0; ti < TESTCASES; ti++) {
    int N = rng() % 100 + 1;
    vector<int> A(N);
    for (auto &&a : A) a = rng() % (1 << 30);
    BinaryTrie<int> trie(1 << 30);
    for (auto &&a : A) trie.insert(a);
    int Q = 100 - rng() % 5;
    vector<int> ans0, ans1;
    for (int i = 0; i < Q; i++) {
      int t = rng() % 2;
      int v = rng() % (1 << 30);
      if (t == 0) {
        int mn = INT_MAX;
        for (auto &&a : A) mn = min(mn, v ^ a);
        ans0.push_back(mn);
        ans1.push_back(trie.minXor(v));
      } else {
        int mx = INT_MIN;
        for (auto &&a : A) mx = max(mx, v ^ a);
        ans0.push_back(mx);
        ans1.push_back(trie.maxXor(v));
      }
    }
    assert(ans0 == ans1);
    for (auto &&a : ans0) checkSum = 31 * checkSum + a;
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 1 Passed" << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  cout << "  Checksum: " << checkSum << endl;
}

int main() {
  test1();
  cout << "Test Passed" << endl;
  return 0;
}


text:
#include <bits/stdc++.h>
#include "../../../../Content/C++/datastructures/trees/fenwicktrees/FenwickTreeAffine.h"
#include "../../../../Content/C++/datastructures/trees/segmenttrees/SegmentTreeAffine.h"
using namespace std;

void test1() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  const int TESTCASES = 1e5;
  long long checkSum = 0;
  for (int ti = 0; ti < TESTCASES; ti++) {
    int N = rng() % 101;
    FenwickTreeAffine<long long> FT(N);
    SegmentTreeAffine<long long> ST(N);
    vector<long long> A(N, 0);
    int Q = N == 0 ? 0 : 100 - rng() % 5;
    vector<long long> ans0, ans1, ans2;
    for (int i = 0; i < Q; i++) {
      int t = rng() % 2;
      int l = rng() % N, r = rng() % N;
      if (l > r) swap(l, r);
      if (t == 0) {
        long long m = rng() % int(1e2) + 1;
        long long b = rng() % int(1e2) + 1;
        for (int j = l; j <= r; j++) A[j] += (j - l + 1) * m + b;
        FT.update(l, r, m, b);
        ST.update(l, r, m, b);
      } else {
        long long sm = 0;
        for (int j = l; j <= r; j++) sm += A[j];
        ans0.push_back(sm);
        ans1.push_back(FT.query(l, r));
        ans2.push_back(ST.query(l, r));
      }
    }
    assert(ans0 == ans1);
    assert(ans0 == ans2);
    for (auto &&a : ans0) checkSum = 31 * checkSum + a;
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 1 Passed" << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  cout << "  Checksum: " << checkSum << endl;
}

int main() {
  test1();
  cout << "Test Passed" << endl;
  return 0;
}


text:
#include <bits/stdc++.h>
#include "../../../../Content/C++/datastructures/trees/fenwicktrees/FenwickTreeAffine.h"
#include "../../../../Content/C++/datastructures/trees/segmenttrees/SegmentTreeAffine.h"
using namespace std;

void test1() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  int N = 2e6;
  FenwickTreeAffine<long long> FT(N);
  int Q = 2e6;
  vector<long long> ans;
  for (int i = 0; i < Q; i++) {
    int t = rng() % 2;
    int l = rng() % N, r = rng() % N;
    if (l > r) swap(l, r);
    if (t == 0) {
      long long m = rng() % int(1e2) + 1;
      long long b = rng() % int(1e2) + 1;
      FT.update(l, r, m, b);
    } else {
      ans.push_back(FT.query(l, r));
    }
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 1 (Fenwick Tree) Passed" << endl;
  cout << "  N: " << N << endl;
  cout << "  Q: " << Q << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  long long checkSum = 0;
  for (auto &&a : ans) checkSum = 31 * checkSum + a;
  cout << "  Checksum: " << checkSum << endl;
}

void test2() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  int N = 2e6;
  SegmentTreeAffine<long long> ST(N);
  int Q = 2e6;
  vector<long long> ans;
  for (int i = 0; i < Q; i++) {
    int t = rng() % 2;
    int l = rng() % N, r = rng() % N;
    if (l > r) swap(l, r);
    if (t == 0) {
      long long m = rng() % int(1e2) + 1;
      long long b = rng() % int(1e2) + 1;
      ST.update(l, r, m, b);
    } else {
      ans.push_back(ST.query(l, r));
    }
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 2 (Segment Tree) Passed" << endl;
  cout << "  N: " << N << endl;
  cout << "  Q: " << Q << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  long long checkSum = 0;
  for (auto &&a : ans) checkSum = 31 * checkSum + a;
  cout << "  Checksum: " << checkSum << endl;
}

int main() {
  test1();
  test2();
  cout << "Test Passed" << endl;
  return 0;
}


text:
#include <bits/stdc++.h>
#include "../../../../../Content/C++/datastructures/trees/segmenttrees/SegmentTreeBottomUp2D.h"
using namespace std;

struct C {
  using Data = long long;
  using Lazy = long long;
  static Data qdef() { return 0; }
  static Data merge(const Data &l, const Data &r) {
    return l + r;
  }
  static Data applyLazy(const Data &l, const Lazy &r) {
    return l + r;
  }
};

void test1() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  int N = 2000;
  int M = 3000;
  vector<vector<long long>> A(N, vector<long long>(M));
  for (auto &&ai : A) for (auto &&aij : ai) aij = rng() % int(1e9) + 1;
  SegmentTreeBottomUp2D<C> ST(A);
  int Q = 1e6;
  vector<long long> ans;
  for (int i = 0; i < Q; i++) {
    int t = rng() % 2;
    if (t == 0) {
      int i = rng() % N, j = rng() % M;
      long long v = rng() % int(1e9) + 1;
      ST.update(i, j, v);
    } else {
      int u = rng() % N, d = rng() % N, l = rng() % M, r = rng() % M;
      if (u > d) swap(u, d);
      if (l > r) swap(l, r);
      ans.push_back(ST.query(u, d, l, r));
    }
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 1 Passed" << endl;
  cout << "  N: " << N << endl;
  cout << "  M: " << M << endl;
  cout << "  Q: " << Q << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  long long checkSum = 0;
  for (auto &&a : ans) checkSum = 31 * checkSum + a;
  cout << "  Checksum: " << checkSum << endl;
}

int main() {
  test1();
  cout << "Test Passed" << endl;
  return 0;
}


text:
#include <bits/stdc++.h>
#include "../../../../../Content/C++/datastructures/trees/segmenttrees/SegmentTreeBottomUp2D.h"
using namespace std;

struct C {
  using Data = long long;
  using Lazy = long long;
  static Data qdef() { return 0; }
  static Data merge(const Data &l, const Data &r) {
    return l + r;
  }
  static Data applyLazy(const Data &l, const Lazy &r) {
    return l + r;
  }
};

void test1() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  const int TESTCASES = 1e5;
  long long checkSum = 0;
  for (int ti = 0; ti < TESTCASES; ti++) {
    int N = rng() % 11;
    int M = rng() % 21;
    vector<vector<long long>> A(N, vector<long long>(M));
    for (auto &&ai : A) for (auto &&aij : ai) aij = rng() % int(1e9) + 1;
    SegmentTreeBottomUp2D<C> ST(A);
    int Q = N == 0 || M == 0 ? 0 : 100 - rng() % 5;
    vector<long long> ans0, ans1;
    for (int i = 0; i < Q; i++) {
      int t = rng() % 2;
      if (t == 0) {
        int i = rng() % N, j = rng() % M;
        long long v = rng() % int(1e9) + 1;
        A[i][j] += v;
        ST.update(i, j, v);
      } else {
        int u = rng() % N, d = rng() % N, l = rng() % M, r = rng() % M;
        if (u > d) swap(u, d);
        if (l > r) swap(l, r);
        long long sm = C::qdef();
        for (int j = u; j <= d; j++) for (int k = l; k <= r; k++) sm += A[j][k];
        ans0.push_back(sm);
        ans1.push_back(ST.query(u, d, l, r));
      }
    }
    assert(ans0 == ans1);
    for (auto &&a : ans0) checkSum = 31 * checkSum + a;
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 1 (2D vector constructor) Passed" << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  cout << "  Checksum: " << checkSum << endl;
}

void test2() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  const int TESTCASES = 1e5;
  long long checkSum = 0;
  for (int ti = 0; ti < TESTCASES; ti++) {
    int N = rng() % 11;
    int M = rng() % 21;
    vector<vector<long long>> A(N, vector<long long>(M));
    for (auto &&ai : A) for (auto &&aij : ai) aij = rng() % int(1e9) + 1;
    SegmentTreeBottomUp2D<C> ST(N, M, 0);
    for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) ST.update(i, j, A[i][j]);
    int Q = N == 0 || M == 0 ? 0 : 100 - rng() % 5;
    vector<long long> ans0, ans1;
    for (int i = 0; i < Q; i++) {
      int t = rng() % 2;
      if (t == 0) {
        int i = rng() % N, j = rng() % M;
        long long v = rng() % int(1e9) + 1;
        A[i][j] += v;
        ST.update(i, j, v);
      } else {
        int u = rng() % N, d = rng() % N, l = rng() % M, r = rng() % M;
        if (u > d) swap(u, d);
        if (l > r) swap(l, r);
        long long sm = C::qdef();
        for (int j = u; j <= d; j++) for (int k = l; k <= r; k++) sm += A[j][k];
        ans0.push_back(sm);
        ans1.push_back(ST.query(u, d, l, r));
      }
    }
    assert(ans0 == ans1);
    for (auto &&a : ans0) checkSum = 31 * checkSum + a;
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 2 (vdef constructor) Passed" << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  cout << "  Checksum: " << checkSum << endl;
}

int main() {
  test1();
  test2();
  cout << "Test Passed" << endl;
  return 0;
}


text:
#include <bits/stdc++.h>
#include "../../../../../Content/C++/datastructures/trees/fenwicktrees/FenwickTree.h"
using namespace std;

void test1() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  int N = 4000;
  int M = 6000;
  vector<vector<long long>> A(N, vector<long long>(M));
  for (auto &&ai : A) for (auto &&aij : ai) aij = rng() % int(1e9) + 1;
  FenwickTree<2, long long> FT(N, M);
  for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) FT.update(i, j, A[i][j]);
  int Q = 1e6;
  vector<long long> ans;
  for (int i = 0; i < Q; i++) {
    int t = rng() % 2;
    if (t == 0) {
      int i = rng() % N, j = rng() % M;
      long long v = rng() % int(1e9) + 1;
      FT.update(i, j, v);
    } else {
      int u = rng() % N, d = rng() % N, l = rng() % M, r = rng() % M;
      if (u > d) swap(u, d);
      if (l > r) swap(l, r);
      ans.push_back(FT.query(u, d, l, r));
    }
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 1 Passed" << endl;
  cout << "  N: " << N << endl;
  cout << "  M: " << M << endl;
  cout << "  Q: " << Q << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  long long checkSum = 0;
  for (auto &&a : ans) checkSum = 31 * checkSum + a;
  cout << "  Checksum: " << checkSum << endl;
}

int main() {
  test1();
  cout << "Test Passed" << endl;
  return 0;
}


text:
#include <bits/stdc++.h>
#include "../../../../../Content/C++/datastructures/trees/fenwicktrees/FenwickTreeRangePoint.h"
#include "../../../../../Content/C++/datastructures/trees/fenwicktrees/FenwickTreeRangePoint1D.h"
using namespace std;

void test1() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  int N = 1e7;
  vector<long long> A(N);
  for (auto &&ai : A) ai = rng() % int(1e9) + 1;
  FenwickTreeRangePoint1D<long long> FT(A);
  int Q = 1e7;
  vector<long long> ans;
  for (int i = 0; i < Q; i++) {
    int t = rng() % 2;
    if (t == 0) {
      int l = rng() % N, r = rng() % N;
      if (l > r) swap(l, r);
      long long v = rng() % int(1e9) + 1;
      FT.update(l, r, v);
    } else {
      int j = rng() % N;
      ans.push_back(FT.get(j));
    }
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 1 (1D vector Constructor) Passed" << endl;
  cout << "  N: " << N << endl;
  cout << "  Q: " << Q << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  long long checkSum = 0;
  for (auto &&a : ans) checkSum = 31 * checkSum + a;
  cout << "  Checksum: " << checkSum << endl;
}

void test2() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  int N = 1e7;
  vector<long long> A(N);
  for (auto &&ai : A) ai = rng() % int(1e9) + 1;
  FenwickTreeRangePoint1D<long long> FT(N);
  for (int i = 0; i < N; i++) FT.update(i, i, A[i]);
  int Q = 1e7;
  vector<long long> ans;
  for (int i = 0; i < Q; i++) {
    int t = rng() % 2;
    if (t == 0) {
      int l = rng() % N, r = rng() % N;
      if (l > r) swap(l, r);
      long long v = rng() % int(1e9) + 1;
      FT.update(l, r, v);
    } else {
      int j = rng() % N;
      ans.push_back(FT.get(j));
    }
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 2 (1D default value constructor) Passed" << endl;
  cout << "  N: " << N << endl;
  cout << "  Q: " << Q << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  long long checkSum = 0;
  for (auto &&a : ans) checkSum = 31 * checkSum + a;
  cout << "  Checksum: " << checkSum << endl;
}

void test3() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  int N = 1e7;
  vector<long long> A(N);
  for (auto &&ai : A) ai = rng() % int(1e9) + 1;
  FenwickTreeRangePoint<1, long long> FT(N);
  for (int i = 0; i < N; i++) FT.update(A[i], i, i);
  int Q = 1e7;
  vector<long long> ans;
  for (int i = 0; i < Q; i++) {
    int t = rng() % 2;
    if (t == 0) {
      int l = rng() % N, r = rng() % N;
      if (l > r) swap(l, r);
      long long v = rng() % int(1e9) + 1;
      FT.update(v, l, r);
    } else {
      int j = rng() % N;
      ans.push_back(FT.get(j));
    }
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 3 (ND) Passed" << endl;
  cout << "  N: " << N << endl;
  cout << "  Q: " << Q << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  long long checkSum = 0;
  for (auto &&a : ans) checkSum = 31 * checkSum + a;
  cout << "  Checksum: " << checkSum << endl;
}

int main() {
  test1();
  test2();
  test3();
  cout << "Test Passed" << endl;
  return 0;
}


text:
#include <bits/stdc++.h>
#include "../../../../../Content/C++/datastructures/trees/fenwicktrees/BitFenwickTree.h"
#include "../../../../../Content/C++/datastructures/trees/fenwicktrees/FenwickTree1D.h"
#include "../../../../../Content/C++/search/BinarySearch.h"
using namespace std;

void test1() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  constexpr const int N = 1e7, Q = 1e7;
  vector<int> A(N);
  for (auto &&ai : A) ai = rng() % 2;
  FenwickTree1D<int> FT(A);
  vector<int> ans;
  ans.reserve(Q);
  for (int i = 0; i < Q; i++) {
    int t = rng() % 2;
    if (t == 0) {
      int i = rng() % N;
      int v = rng() % 2;
      FT.update(i, v - A[i]);
      A[i] = v;
    } else {
      int l = rng() % N, r = rng() % N;
      if (l > r) swap(l, r);
      ans.push_back(FT.query(l, r));
    }
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 1 (Fenwick Tree) Passed" << endl;
  cout << "  N: " << N << endl;
  cout << "  Q: " << Q << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  long long checkSum = 0;
  for (auto &&a : ans) checkSum = 31 * checkSum + a;
  cout << "  Checksum: " << checkSum << endl;
}

void test2() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  constexpr const int N = 1e7, Q = 1e7;
  BitFenwickTree BFT(N);
  for (int i = 0; i < N; i++) BFT.set(i, rng() % 2);
  BFT.build();
  vector<int> ans;
  ans.reserve(Q);
  for (int i = 0; i < Q; i++) {
    int t = rng() % 2;
    if (t == 0) {
      int i = rng() % N;
      int v = rng() % 2;
      BFT.update(i, v);
    } else {
      int l = rng() % N, r = rng() % N;
      if (l > r) swap(l, r);
      ans.push_back(BFT.query(l, r));
    }
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 2 (Bit Fenwick Tree) Passed" << endl;
  cout << "  N: " << N << endl;
  cout << "  Q: " << Q << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  long long checkSum = 0;
  for (auto &&a : ans) checkSum = 31 * checkSum + a;
  cout << "  Checksum: " << checkSum << endl;
}

void test3() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  constexpr const int N = 1e9, Q = 1e7;
  BitFenwickTree BFT(N);
  for (int i = 0; i < N; i++) BFT.set(i, rng() % 2);
  BFT.build();
  vector<int> ans;
  ans.reserve(Q);
  for (int i = 0; i < Q; i++) {
    int t = rng() % 2;
    if (t == 0) {
      int i = rng() % N;
      int v = rng() % 2;
      BFT.update(i, v);
    } else {
      int l = rng() % N, r = rng() % N;
      if (l > r) swap(l, r);
      ans.push_back(BFT.query(l, r));
    }
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 3 (Bit Fenwick Tree) Passed" << endl;
  cout << "  N: " << N << endl;
  cout << "  Q: " << Q << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  long long checkSum = 0;
  for (auto &&a : ans) checkSum = 31 * checkSum + a;
  cout << "  Checksum: " << checkSum << endl;
}

void test4() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  constexpr const int N = 1e7, Q = 1e7;
  vector<int> A(N);
  for (auto &&ai : A) ai = rng() % 2;
  FenwickTree1D<int> FT(A);
  vector<int> ans;
  ans.reserve(Q);
  for (int i = 0; i < Q; i++) {
    int t = rng() % 4;
    if (t == 0) {
      int i = rng() % N;
      int v = rng() % 2;
      FT.update(i, v - A[i]);
      A[i] = v;
    } else if (t == 1) {
      int l = rng() % N, r = rng() % N;
      if (l > r) swap(l, r);
      ans.push_back(FT.query(l, r));
    } else if (t == 2) {
      int TOT = FT.query(N - 1) * 2 + 1;
      int v = rng() % TOT;
      ans.push_back(FT.bsearch(v, less<int>()));
    } else if (t == 3) {
      int TOT = FT.query(N - 1) * 2 + 1;
      int v = rng() % TOT;
      ans.push_back(FT.bsearch(v, less_equal<int>()));
    }
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 4 (Fenwick Tree, lower_bound, upper_bound) Passed" << endl;
  cout << "  N: " << N << endl;
  cout << "  Q: " << Q << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  long long checkSum = 0;
  for (auto &&a : ans) checkSum = 31 * checkSum + a;
  cout << "  Checksum: " << checkSum << endl;
}

void test5() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  constexpr const int N = 1e7, Q = 1e7;
  BitFenwickTree BFT(N);
  for (int i = 0; i < N; i++) BFT.set(i, rng() % 2);
  BFT.build();
  vector<int> ans;
  ans.reserve(Q);
  for (int i = 0; i < Q; i++) {
    int t = rng() % 4;
    if (t == 0) {
      int i = rng() % N;
      int v = rng() % 2;
      BFT.update(i, v);
    } else if (t == 1) {
      int l = rng() % N, r = rng() % N;
      if (l > r) swap(l, r);
      ans.push_back(BFT.query(l, r));
    } else if (t == 2) {
      int TOT = BFT.query(N - 1) * 2 + 1;
      int v = rng() % TOT;
      ans.push_back(BFT.bsearch(v, less<int>()));
    } else if (t == 3) {
      int TOT = BFT.query(N - 1) * 2 + 1;
      int v = rng() % TOT;
      ans.push_back(BFT.bsearch(v, less_equal<int>()));
    }
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 5 (Bit Fenwick Tree, lower_bound, upper_bound) Passed" << endl;
  cout << "  N: " << N << endl;
  cout << "  Q: " << Q << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  long long checkSum = 0;
  for (auto &&a : ans) checkSum = 31 * checkSum + a;
  cout << "  Checksum: " << checkSum << endl;
}

void test6() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  constexpr const int N = 1e7, Q = 1e7;
  BitFenwickTree BFT(N);
  for (int i = 0; i < N; i++) BFT.set(i, rng() % 2);
  BFT.build();
  vector<int> ans;
  ans.reserve(Q);
  for (int i = 0; i < Q; i++) {
    int t = rng() % 4;
    if (t == 0) {
      int i = rng() % N;
      int v = rng() % 2;
      BFT.update(i, v);
    } else if (t == 1) {
      int l = rng() % N, r = rng() % N;
      if (l > r) swap(l, r);
      ans.push_back(BFT.query(l, r));
    } else if (t == 2) {
      int TOT = BFT.query(N - 1) * 2 + 1;
      int v = rng() % TOT;
      ans.push_back(bsearch<FIRST>(0, N, [&] (int k) {
        return BFT.query(k) >= v;
      }));
    } else if (t == 3) {
      int TOT = BFT.query(N - 1) * 2 + 1;
      int v = rng() % TOT;
      ans.push_back(bsearch<FIRST>(0, N, [&] (int k) {
        return BFT.query(k) > v;
      }));
    }
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 6 (Bit Fenwick Tree, bsearch with query) Passed" << endl;
  cout << "  N: " << N << endl;
  cout << "  Q: " << Q << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  long long checkSum = 0;
  for (auto &&a : ans) checkSum = 31 * checkSum + a;
  cout << "  Checksum: " << checkSum << endl;
}

int main() {
  test1();
  test2();
  test3();
  test4();
  test5();
  test6();
  cout << "Test Passed" << endl;
  return 0;
}


text:
#include <bits/stdc++.h>
#include "../../../../../Content/C++/datastructures/trees/fenwicktrees/BitFenwickTree.h"
#include "../../../../../Content/C++/datastructures/trees/fenwicktrees/FenwickTree1D.h"
using namespace std;

void test1() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  const int TESTCASES = 5e4;
  long long checkSum = 0;
  for (int ti = 0; ti < TESTCASES; ti++) {
    int N = rng() % 1001;
    vector<int> A(N);
    for (auto &&ai : A) ai = rng() % 2;
    FenwickTree1D<int> FT(A);
    BitFenwickTree BFT(N);
    for (int i = 0; i < N; i++) BFT.set(i, A[i]);
    BFT.build();
    int Q = N == 0 ? 0 : 1000 - rng() % 5;
    vector<int> ans0, ans1;
    for (int i = 0; i < Q; i++) {
      int t = rng() % 2;
      if (t == 0) {
        int i = rng() % N;
        int v = rng() % 2;
        FT.update(i, v - A[i]);
        A[i] = v;
        BFT.update(i, v);
      } else {
        int l = rng() % N, r = rng() % N;
        if (l > r) swap(l, r);
        ans0.push_back(FT.query(l, r));
        ans1.push_back(BFT.query(l, r));
      }
    }
    assert(ans0 == ans1);
    for (auto &&a : ans0) checkSum = 31 * checkSum + a;
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 1 (point update, range query) Passed" << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  cout << "  Checksum: " << checkSum << endl;
}

void test2() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  const int TESTCASES = 5e4;
  long long checkSum = 0;
  for (int ti = 0; ti < TESTCASES; ti++) {
    int N = rng() % 1001;
    vector<int> A(N);
    for (auto &&ai : A) ai = rng() % 2;
    FenwickTree1D<int> FT(A);
    BitFenwickTree BFT(N);
    for (int i = 0; i < N; i++) BFT.set(i, A[i]);
    BFT.build();
    int Q = N == 0 ? 0 : 1000 - rng() % 5;
    vector<int> ans0, ans1;
    for (int i = 0; i < Q; i++) {
      int t = rng() % 4;
      if (t == 0) {
        int i = rng() % N;
        int v = rng() % 2;
        FT.update(i, v - A[i]);
        A[i] = v;
        BFT.update(i, v);
      } else if (t == 1) {
        int l = rng() % N, r = rng() % N;
        if (l > r) swap(l, r);
        ans0.push_back(FT.query(l, r));
        ans1.push_back(BFT.query(l, r));
      } else if (t == 2) {
        int TOT = FT.query(N - 1) * 2 + 1;
        int v = rng() % TOT;
        ans0.push_back(FT.bsearch(v, less<int>()));
        ans1.push_back(BFT.bsearch(v, less<int>()));
      } else if (t == 3) {
        int TOT = FT.query(N - 1) * 2 + 1;
        int v = rng() % TOT;
        ans0.push_back(FT.bsearch(v, less_equal<int>()));
        ans1.push_back(BFT.bsearch(v, less_equal<int>()));
      }
    }
    assert(ans0 == ans1);
    for (auto &&a : ans0) checkSum = 31 * checkSum + a;
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 2 (point update, range query, binary search) Passed" << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  cout << "  Checksum: " << checkSum << endl;
}

int main() {
  test1();
  test2();
  cout << "Test Passed" << endl;
  return 0;
}


text:
#include <bits/stdc++.h>
#include "../../../../../Content/C++/datastructures/trees/fenwicktrees/RangeAddRangeSum2D.h"
using namespace std;

void test1() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  int N = 2000;
  int M = 3000;
  RangeAddRangeSum2D<long long> ST(N, M);
  int Q = 1e5;
  vector<long long> ans;
  for (int i = 0; i < Q; i++) {
    int t = rng() % 2;
    int u = rng() % N, d = rng() % N, l = rng() % M, r = rng() % M;
    if (u > d) swap(u, d);
    if (l > r) swap(l, r);
    if (t == 0) {
      long long v = rng() % int(1e9) + 1;
      ST.update(u, d, l, r, v);
    } else {
      ans.push_back(ST.query(u, d, l, r));
    }
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 1 Passed" << endl;
  cout << "  N: " << N << endl;
  cout << "  M: " << M << endl;
  cout << "  Q: " << Q << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  long long checkSum = 0;
  for (auto &&a : ans) checkSum = 31 * checkSum + a;
  cout << "  Checksum: " << checkSum << endl;
}

int main() {
  test1();
  cout << "Test Passed" << endl;
  return 0;
}


text:
#include <bits/stdc++.h>
#include "../../../../../Content/C++/datastructures/trees/fenwicktrees/FenwickTreeRangePoint.h"
using namespace std;

void test1() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  const int TESTCASES = 1e5;
  long long checkSum = 0;
  for (int ti = 0; ti < TESTCASES; ti++) {
    int N = rng() % 11;
    int M = rng() % 21;
    vector<vector<long long>> A(N, vector<long long>(M));
    for (auto &&ai : A) for (auto &&aij : ai) aij = rng() % int(1e9) + 1;
    FenwickTreeRangePoint<2, long long> FT(N, M);
    for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) FT.update(A[i][j], i, i, j, j);
    int Q = N == 0 || M == 0 ? 0 : 100 - rng() % 5;
    vector<long long> ans0, ans1;
    for (int i = 0; i < Q; i++) {
      int t = rng() % 2;
      if (t == 0) {
        int u = rng() % N, d = rng() % N, l = rng() % M, r = rng() % M;
        if (u > d) swap(u, d);
        if (l > r) swap(l, r);
        long long v = rng() % int(1e9) + 1;
        for (int j = u; j <= d; j++) for (int k = l; k <= r; k++) A[j][k] += v;
        FT.update(v, u, d, l, r);
      } else {
        int i = rng() % N, j = rng() % M;
        ans0.push_back(A[i][j]);
        ans1.push_back(FT.get(i, j));
      }
    }
    assert(ans0 == ans1);
    for (auto &&a : ans0) checkSum = 31 * checkSum + a;
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 1 Passed" << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  cout << "  Checksum: " << checkSum << endl;
}

int main() {
  test1();
  cout << "Test Passed" << endl;
  return 0;
}


text:
#include <bits/stdc++.h>
#include "../../../../../Content/C++/datastructures/trees/fenwicktrees/FenwickTree.h"
#include "../../../../../Content/C++/datastructures/trees/fenwicktrees/FenwickTree1D.h"
#include "../../../../../Content/C++/search/BinarySearch.h"
using namespace std;

void test1() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  const int TESTCASES = 1e5;
  long long checkSum = 0;
  for (int ti = 0; ti < TESTCASES; ti++) {
    int N = rng() % 101;
    vector<long long> A(N);
    for (auto &&ai : A) ai = rng() % int(1e9) + 1;
    FenwickTree1D<long long> FT1(N);
    FenwickTree1D<long long> FT2(A);
    FenwickTree<1, long long> FT3(N);
    for (int i = 0; i < N; i++) {
      FT1.update(i, A[i]);
      FT3.update(i, A[i]);
    }
    int Q = N == 0 ? 0 : 100 - rng() % 5;
    vector<long long> ans0, ans1, ans2, ans3;
    for (int i = 0; i < Q; i++) {
      int t = rng() % 2;
      if (t == 0) {
        int i = rng() % N;
        long long v = rng() % int(1e9) + 1;
        A[i] += v;
        FT1.update(i, v);
        FT2.update(i, v);
        FT3.update(i, v);
      } else {
        int l = rng() % N, r = rng() % N;
        if (l > r) swap(l, r);
        long long sm = 0;
        for (int j = l; j <= r; j++) sm += A[j];
        ans0.push_back(sm);
        ans1.push_back(FT1.query(l, r));
        ans2.push_back(FT2.query(l, r));
        ans3.push_back(FT3.query(l, r));
      }
    }
    vector<long long> A1 = FT1.values(), A2 = FT2.values();
    assert(ans0 == ans1);
    assert(ans0 == ans2);
    assert(ans0 == ans3);
    assert(A == A1);
    assert(A == A2);
    for (auto &&a : ans0) checkSum = 31 * checkSum + a;
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 1 (point update, range query) Passed" << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  cout << "  Checksum: " << checkSum << endl;
}

void test2() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  const int TESTCASES = 1e5;
  long long checkSum = 0;
  for (int ti = 0; ti < TESTCASES; ti++) {
    int maxVal = pow(10, rng() % 10);
    int N = rng() % 101;
    vector<long long> A(N);
    for (auto &&ai : A) ai = rng() % maxVal + 1;
    FenwickTree1D<long long> FT1(N);
    FenwickTree1D<long long> FT2(A);
    for (int i = 0; i < N; i++) FT1.update(i, A[i]);
    int Q = N == 0 ? 0 : 100 - rng() % 5;
    vector<long long> ans0, ans1, ans2, ans3;
    for (int i = 0; i < Q; i++) {
      int t = rng() % 4;
      if (t == 0) {
        int i = rng() % N;
        long long v = rng() % maxVal + 1;
        A[i] += v;
        FT1.update(i, v);
        FT2.update(i, v);
      } else if (t == 1) {
        int l = rng() % N, r = rng() % N;
        if (l > r) swap(l, r);
        long long sm = 0;
        for (int j = l; j <= r; j++) sm += A[j];
        ans0.push_back(sm);
        ans1.push_back(FT1.query(l, r));
        ans2.push_back(FT2.query(l, r));
        ans3.push_back(ans2.back());
      } else if (t == 2) {
        long long TOT = FT1.query(N - 1) * 2 + 1;
        long long v = rng() % TOT;
        int j = 0;
        long long sm = 0;
        while (j < N && sm + A[j] < v) sm += A[j++];
        ans0.push_back(j);
        ans1.push_back(FT1.bsearch(v, less<long long>()));
        ans2.push_back(FT2.bsearch(v, less<long long>()));
        ans3.push_back(bsearch<FIRST>(0, N, [&] (int k) {
          return FT2.query(k) >= v;
        }));
      } else {
        long long TOT = FT1.query(N - 1) * 2 + 1;
        long long v = rng() % TOT;
        int j = 0;
        long long sm = 0;
        while (j < N && sm + A[j] <= v) sm += A[j++];
        ans0.push_back(j);
        ans1.push_back(FT1.bsearch(v, less_equal<long long>()));
        ans2.push_back(FT2.bsearch(v, less_equal<long long>()));
        ans3.push_back(bsearch<FIRST>(0, N, [&] (int k) {
          return FT2.query(k) > v;
        }));
      }
    }
    vector<long long> A1 = FT1.values(), A2 = FT2.values();
    assert(ans0 == ans1);
    assert(ans0 == ans2);
    assert(ans0 == ans3);
    assert(A == A1);
    assert(A == A2);
    for (auto &&a : ans0) checkSum = 31 * checkSum + a;
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 2 (point update, range query, binary search) Passed" << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  cout << "  Checksum: " << checkSum << endl;
}

int main() {
  test1();
  test2();
  cout << "Test Passed" << endl;
  return 0;
}


text:
#include <bits/stdc++.h>
#include "../../../../../Content/C++/datastructures/trees/fenwicktrees/FenwickTreeRange1D.h"
using namespace std;

void test1() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  int N = 5e6;
  vector<long long> A(N);
  for (auto &&ai : A) ai = rng() % int(1e4) + 1;
  FenwickTreeRange1D<long long> FT(A);
  int Q = 5e6;
  vector<long long> ans;
  for (int i = 0; i < Q; i++) {
    int t = rng() % 2;
    if (t == 0) {
      int l = rng() % N, r = rng() % N;
      if (l > r) swap(l, r);
      long long v = rng() % int(1e4) + 1;
      FT.update(l, r, v);
    } else {
      int l = rng() % N, r = rng() % N;
      if (l > r) swap(l, r);
      ans.push_back(FT.query(l, r));
    }
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 1 Passed" << endl;
  cout << "  N: " << N << endl;
  cout << "  Q: " << Q << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  long long checkSum = 0;
  for (auto &&a : ans) checkSum = 31 * checkSum + a;
  cout << "  Checksum: " << checkSum << endl;
}

int main() {
  test1();
  cout << "Test Passed" << endl;
  return 0;
}


text:
#include <bits/stdc++.h>
#include "../../../../../Content/C++/datastructures/trees/fenwicktrees/RangeAddRangeSum2D.h"
using namespace std;

void test1() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  const int TESTCASES = 1e4;
  long long checkSum = 0;
  for (int ti = 0; ti < TESTCASES; ti++) {
    int N = rng() % 21;
    int M = rng() % 21;
    vector<vector<long long>> A(N, vector<long long>(M, 0));
    RangeAddRangeSum2D<long long> ST(N, M);
    int Q = N == 0 || M == 0 ? 0 : 100 - rng() % 5;
    vector<long long> ans0, ans1;
    for (int i = 0; i < Q; i++) {
      int t = rng() % 2;
      int u = rng() % N, d = rng() % N, l = rng() % M, r = rng() % M;
      if (u > d) swap(u, d);
      if (l > r) swap(l, r);
      if (t == 0) {
        long long v = rng() % int(1e9) + 1;
        for (int j = u; j <= d; j++) for (int k = l; k <= r; k++) A[j][k] += v;
        ST.update(u, d, l, r, v);
      } else {
        long long sm = 0;
        for (int j = u; j <= d; j++) for (int k = l; k <= r; k++) sm += A[j][k];
        ans0.push_back(sm);
        ans1.push_back(ST.query(u, d, l, r));
      }
    }
    assert(ans0 == ans1);
    for (auto &&a : ans0) checkSum = 31 * checkSum + a;
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 1 Passed" << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  cout << "  Checksum: " << checkSum << endl;
}

int main() {
  test1();
  cout << "Test Passed" << endl;
  return 0;
}


text:
#include <bits/stdc++.h>
#include "../../../../../Content/C++/datastructures/trees/fenwicktrees/FenwickTreeRangePoint.h"
#include "../../../../../Content/C++/datastructures/trees/fenwicktrees/FenwickTreeRangePoint1D.h"
using namespace std;

void test1() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  const int TESTCASES = 1e5;
  long long checkSum = 0;
  for (int ti = 0; ti < TESTCASES; ti++) {
    int N = rng() % 101;
    vector<long long> A(N);
    for (auto &&ai : A) ai = rng() % int(1e9) + 1;
    FenwickTreeRangePoint1D<long long> FT1(N);
    FenwickTreeRangePoint1D<long long> FT2(A);
    FenwickTreeRangePoint<1, long long> FT3(N);
    for (int i = 0; i < N; i++) {
      FT1.update(i, i, A[i]);
      FT3.update(A[i], i, i);
    }
    int Q = N == 0 ? 0 : 100 - rng() % 5;
    vector<long long> ans0, ans1, ans2, ans3;
    for (int i = 0; i < Q; i++) {
      int t = rng() % 2;
      if (t == 0) {
        int l = rng() % N, r = rng() % N;
        if (l > r) swap(l, r);
        long long v = rng() % int(1e9) + 1;
        for (int j = l; j <= r; j++) A[j] += v;
        FT1.update(l, r, v);
        FT2.update(l, r, v);
        FT3.update(v, l, r);
      } else {
        int j = rng() % N;
        ans0.push_back(A[j]);
        ans1.push_back(FT1.get(j));
        ans2.push_back(FT2.get(j));
        ans3.push_back(FT3.get(j));
      }
    }
    vector<long long> A1 = FT1.values(), A2 = FT2.values();
    assert(ans0 == ans1);
    assert(ans0 == ans2);
    assert(ans0 == ans3);
    assert(A == A1);
    assert(A == A2);
    for (auto &&a : ans0) checkSum = 31 * checkSum + a;
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 1 Passed" << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  cout << "  Checksum: " << checkSum << endl;
}

int main() {
  test1();
  cout << "Test Passed" << endl;
  return 0;
}