-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathfenwick.hpp
More file actions
34 lines (29 loc) · 772 Bytes
/
Copy pathfenwick.hpp
File metadata and controls
34 lines (29 loc) · 772 Bytes
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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
// Lightweight Fenwick Tree (Binary Indexed Tree)
// Supports point updates and prefix sum queries.
template <class T>
struct fenwick {
// internal array of size n
vector <T> data;
// create tree for n elements initialized with zeros
fenwick(int n) {
data.resize(n);
}
// add "val" to position "pos"
void add(int pos, T val) {
for (; pos < data.size(); pos |= pos + 1) {
data[pos] = data[pos] + val;
}
}
// get sum of range [0, r]
T get(int r) const {
T res{};
for (; r >= 0; r &= r + 1, --r) {
res = res + data[r];
}
return res;
}
};