Skip to content

Commit cbd2669

Browse files
committed
This works locally.
1 parent 8259ac5 commit cbd2669

File tree

1 file changed

+61
-61
lines changed

1 file changed

+61
-61
lines changed

src/data_structures/fenwick.md

Lines changed: 61 additions & 61 deletions
Original file line numberDiff line numberDiff line change
@@ -165,38 +165,38 @@ Also this implementation supports two constructors.
165165
You can create a Fenwick tree initialized with zeros, or you can convert an existing array into the Fenwick form.
166166

167167
=== "C++"
168-
```{.cpp file=fenwick_sum}
169-
struct FenwickTree {
170-
vector<int> bit; // binary indexed tree
171-
int n;
172-
173-
FenwickTree(int n) {
174-
this->n = n;
175-
bit.assign(n, 0);
176-
}
177-
178-
FenwickTree(vector<int> const &a) : FenwickTree(a.size()) {
179-
for (size_t i = 0; i < a.size(); i++)
180-
add(i, a[i]);
181-
}
182-
183-
int sum(int r) {
184-
int ret = 0;
185-
for (; r >= 0; r = (r & (r + 1)) - 1)
186-
ret += bit[r];
187-
return ret;
188-
}
189-
190-
int sum(int l, int r) {
191-
return sum(r) - sum(l - 1);
192-
}
193-
194-
void add(int idx, int delta) {
195-
for (; idx < n; idx = idx | (idx + 1))
196-
bit[idx] += delta;
197-
}
198-
};
199-
```
168+
```{.cpp file=fenwick_sum}
169+
struct FenwickTree {
170+
vector<int> bit; // binary indexed tree
171+
int n;
172+
173+
FenwickTree(int n) {
174+
this->n = n;
175+
bit.assign(n, 0);
176+
}
177+
178+
FenwickTree(vector<int> const &a) : FenwickTree(a.size()) {
179+
for (size_t i = 0; i < a.size(); i++)
180+
add(i, a[i]);
181+
}
182+
183+
int sum(int r) {
184+
int ret = 0;
185+
for (; r >= 0; r = (r & (r + 1)) - 1)
186+
ret += bit[r];
187+
return ret;
188+
}
189+
190+
int sum(int l, int r) {
191+
return sum(r) - sum(l - 1);
192+
}
193+
194+
void add(int idx, int delta) {
195+
for (; idx < n; idx = idx | (idx + 1))
196+
bit[idx] += delta;
197+
}
198+
};
199+
```
200200
=== "Python"
201201
```py
202202
class FenwickTree:
@@ -253,35 +253,35 @@ Additionally, each time a value is `update`'d, the new value has to be smaller t
253253
Both significant limitations are because the $min$ operation together with the set of integers doesn't form a group, as there are no inverse elements.
254254
255255
=== "C++"
256-
```{.cpp file=fenwick_min}
257-
struct FenwickTreeMin {
258-
vector<int> bit;
259-
int n;
260-
const int INF = (int)1e9;
261-
262-
FenwickTreeMin(int n) {
263-
this->n = n;
264-
bit.assign(n, INF);
265-
}
266-
267-
FenwickTreeMin(vector<int> a) : FenwickTreeMin(a.size()) {
268-
for (size_t i = 0; i < a.size(); i++)
269-
update(i, a[i]);
270-
}
271-
272-
int getmin(int r) {
273-
int ret = INF;
274-
for (; r >= 0; r = (r & (r + 1)) - 1)
275-
ret = min(ret, bit[r]);
276-
return ret;
277-
}
278-
279-
void update(int idx, int val) {
280-
for (; idx < n; idx = idx | (idx + 1))
281-
bit[idx] = min(bit[idx], val);
282-
}
283-
};
284-
```
256+
```{.cpp file=fenwick_min}
257+
struct FenwickTreeMin {
258+
vector<int> bit;
259+
int n;
260+
const int INF = (int)1e9;
261+
262+
FenwickTreeMin(int n) {
263+
this->n = n;
264+
bit.assign(n, INF);
265+
}
266+
267+
FenwickTreeMin(vector<int> a) : FenwickTreeMin(a.size()) {
268+
for (size_t i = 0; i < a.size(); i++)
269+
update(i, a[i]);
270+
}
271+
272+
int getmin(int r) {
273+
int ret = INF;
274+
for (; r >= 0; r = (r & (r + 1)) - 1)
275+
ret = min(ret, bit[r]);
276+
return ret;
277+
}
278+
279+
void update(int idx, int val) {
280+
for (; idx < n; idx = idx | (idx + 1))
281+
bit[idx] = min(bit[idx], val);
282+
}
283+
};
284+
```
285285
=== "Python"
286286
```py
287287
class FenwickTreeMin:

0 commit comments

Comments
 (0)