1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
|
const int n = 10000; // ALL INDICES START AT 1 WITH THIS CODE!!
// mode 1: update indices, read prefixes
void update_idx(int tree[], int i, int val) { // v[i] += val
for (; i <= n; i += i & -i) tree[i] += val;
}
int read_prefix(int tree[], int i) { // get sum v[1..i]
int sum = 0;
for (; i > 0; i -= i & -i) sum += tree[i];
return sum;
}
int kth(int k) { // find kth element in tree (1-based index)
int ans = 0;
for (int i = maxl; i >= 0; --i) // maxl = largest i s.t. (1<<i) <= n
if (ans + (1<<i) <= n && tree[ans + (1<<i)] < k) {
ans += 1<<i;
k -= tree[ans];
}
return ans+1;
}
// mode 2: update prefixes, read indices
void update_prefix(int tree[], int i, int val) { // v[1..i] += val
for (; i > 0; i -= i & -i) tree[i] += val;
}
int read_idx(int tree[], int i) { // get v[i]
int sum = 0;
for (; i <= n; i += i & -i) sum += tree[i];
return sum;
}
// mode 3: range-update range-query
const int maxn = 100100;
int n;
ll mul[maxn], add[maxn];
void update_idx(ll tree[], int x, ll val) {
for (int i = x; i <= n; i += i & -i) tree[i] += val;
}
void update_prefix(int x, ll val) { // v[x] += val
update_idx(mul, 1, val);
update_idx(mul, x + 1, -val);
update_idx(add, x + 1, x * val);
}
ll read_prefix(int x) { // get sum v[1..x]
ll a = 0, b = 0;
for (int i = x; i > 0; i -= i & -i) a += mul[i], b += add[i];
return a * x + b;
}
void update_range(int l, int r, ll val) { // v[l..r] += val
update_prefix(l - 1, -val);
update_prefix(r, val);
}
ll read_range(int l, int r) { // get sum v[l..r]
return read_prefix(r) - read_prefix(l - 1);
}
|
