@@ -165,38 +165,38 @@ Also this implementation supports two constructors.
165165You 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
253253Both 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