The number of inversions
An array of n different numbers from 1 to n is given (a permutation, n ≤ 2·105). An inversion is a pair i < j for which a[i] > a[j]. How many inversions are there?
Example
Input
5
2 4 1 3 5Output
3A Fenwick tree (Binary Indexed Tree) maintains an array and answers the question "what is the sum of the first k elements?" – even while the elements change. Both operations take O(log n), and the code is short: about ten lines.
An array of n numbers and q queries of two kinds are given: change the element at position i and what is the sum on the interval [l, r]. An ordinary array gives an update in O(1) and a sum in O(n). Prefix sums give a sum in O(1) but an update in O(n). For n, q up to 2·105 both approaches are too slow, while a Fenwick tree does both queries in O(log n).
The positions are from 1 to n. The element bit[i] keeps the sum of the part of the array that ends at i, and the length of that part is the lowest bit of the number i: lowbit(i) = i & (-i). For example, bit[12] keeps the sum of positions 9–12 (12 = 1100₂, the lowest bit is 4), and bit[7] only position 7.
bit[i], then go to i -= lowbit(i), while i > 0.bit[i], then go to i += lowbit(i), while i ≤ n.In both cases the number of steps is at most the number of bits, i.e. O(log n).
#include <iostream>
#include <vector>
using namespace std;
int n;
vector<long long> bit;
void add(int i, long long x) { // a[i] += x
for (; i <= n; i += i & (-i)) bit[i] += x;
}
long long prefixSum(int i) { // a[1] + ... + a[i]
long long s = 0;
for (; i > 0; i -= i & (-i)) s += bit[i];
return s;
}
int main() {
int q;
cin >> n >> q;
bit.assign(n + 1, 0);
vector<long long> a(n + 1);
for (int i = 1; i <= n; i++) { cin >> a[i]; add(i, a[i]); }
while (q--) {
int type;
cin >> type;
if (type == 1) { // 1 i v : a[i] = v
int i; long long v;
cin >> i >> v;
add(i, v - a[i]); // we add the difference
a[i] = v;
} else { // 2 l r : the sum a[l..r]
int l, r;
cin >> l >> r;
cout << prefixSum(r) - prefixSum(l - 1) << "\n";
}
}
return 0;
}
The update "set to v" is turned into "add the difference v − a[i]", which is why we also keep the array a itself.
A Fenwick tree is shorter and faster, but it naturally works only for operations that have an "inverse" (sum – subtraction, XOR). For the minimum, the maximum or more complex queries on an interval, a segment tree is used.
Every task has an example, a hint and a solution. The solutions have been checked on the examples from the text.
An array of n different numbers from 1 to n is given (a permutation, n ≤ 2·105). An inversion is a pair i < j for which a[i] > a[j]. How many inversions are there?
5
2 4 1 3 53A shop records sales for n days (initially 0). Queries: A d k – on day d another k items were sold; S a b – how many items were sold in total from day a to day b?
5 4
A 2 3
A 4 5
S 1 3
S 2 53
8prefixSum(r) − prefixSum(l − 1).int – use long long.1. What is 12 & (-12)?
2. What is the complexity of a query for the sum of the first k elements?
3. Which query does a Fenwick tree not support directly?