Fenwick inversions

Questions 1 to 5 of 7

1. 1. Predict the output of this program. It prints one line with two numbers. ``cpp #include <algorithm> #include <iostream> #include <vector> using namespace std; class Fenwick { public: explicit Fenwick(int n) : n_(n), tree_(n + 1, 0) {} void add(int pos, int delta) { for (; pos <= n_; pos += pos & -pos) tree_[pos] += delta; } int prefix(int pos) const { int total = 0; for (; pos > 0; pos -= pos & -pos) total += tree_[pos]; return total; } private: int n_; vector<int> tree_; }; long long countInversions(const vector<int>& a) { vector<int> sorted_values = a; sort(sorted_values.begin(), sorted_values.end()); sorted_values.erase(unique(sorted_values.begin(), sorted_values.end()), sorted_values.end()); Fenwick seen(static_cast<int>(sorted_values.size())); long long inversions = 0; int processed = 0; for (int x : a) { int rank = static_cast<int>(lower_bound(sorted_values.begin(), sorted_values.end(), x) - sorted_values.begin()) + 1; inversions += processed - seen.prefix(rank); seen.add(rank, 1); ++processed; } return inversions; } int main() { cout << countInversions({5, 1, 4, 2, 3}) << ' ' << countInversions({2, 2, 1}) << '\n'; } ``

   5 26 16 210 2
2. 2. Predict the output of this program. It prints one line with three numbers. ``cpp #include <iostream> #include <vector> class Fenwick { public: explicit Fenwick(int n) : n_(n), tree_(n + 1, 0) {} void add(int pos, int delta) { for (; pos <= n_; pos += pos & -pos) tree_[pos] += delta; } int prefix(int pos) const { int total = 0; for (; pos > 0; pos -= pos & -pos) total += tree_[pos]; return total; } private: int n_; std::vector<int> tree_; }; int main() { Fenwick f(6); f.add(2, 1); f.add(4, 1); f.add(5, 1); std::cout << f.prefix(4) << ' ' << f.prefix(1) << ' ' << f.prefix(6) << '\n'; } ``

   3 0 22 0 32 1 31 0 3
3. 3. How many comparisons does the slow pair-by-pair method make on 100,000 distinct numbers?

   Type a number.

4. 4. What is the running time of the sweep method with a Fenwick tree, for n values?

   O(n^2)O(n)O(log n)O(n log n)
5. 5. In the sweep loop, the program reads seen.prefix(rank) first and then calls seen.add(rank, 1). Why is the order important?

   If the add ran first, x would count as an earlier value that is at most x, so every count would be one too smallIf the add ran first, the tree would grow past the size it was built withIf the add ran first, equal values would be counted as inversionsIf the add ran first, the rank of x would change for the next element