GCC Code Coverage Report

Directory: ./
Coverage: low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%
Coverage Exec / Excl / Total
Lines: 100.0% 26 / 0 / 26
Functions: 100.0% 12 / 0 / 12
Branches: 68.2% 30 / 0 / 44
src/ds/fenwick/d2/lib.hpp
Line Branch Exec Source
1 #pragma once
2
3 #include "../../../bit/lowbit/lib.hpp"
4 #include "../../../util/alias/others/lib.hpp"
5
6 namespace tifa_libs {
7
8 template <class T>
9 class fenwick2d {
10 vvec<T> a;
11
12 public:
13 //! [1, row) * [1, col)
14
4/8
tifa_libs::fenwick2d<int>::fenwick2d(unsigned int, unsigned int):
✓ Branch 3 taken 10 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 10 times.
✗ Branch 6 not taken.
tifa_libs::fenwick2d<unsigned int>::fenwick2d(unsigned int, unsigned int):
✓ Branch 3 taken 30 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 30 times.
✗ Branch 6 not taken.
 120 CEXPE fenwick2d(u32 row, u32 col) NE : a(row, vec<T>(col)) { assert(row > 1 && col > 1); }
15
16 43310678 ND CEXP u32 row() CNE { return (u32)a.size(); }
17 215191548 ND CEXP u32 col() CNE { return (u32)a[0].size(); }
18 //! [x, row) * [y, col), x > 0, y > 0
19 1746424 CEXP void add(u32 x, u32 y, cT_(T) v) NE {
20
10/20
tifa_libs::fenwick2d<int>::add(unsigned int, unsigned int, int):
✓ Branch 0 taken 2660 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 2660 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 2660 times.
✗ Branch 6 not taken.
✗ Branch 8 not taken.
✓ Branch 9 taken 2660 times.
✗ Branch 10 not taken.
✓ Branch 11 taken 2660 times.
tifa_libs::fenwick2d<unsigned int>::add(unsigned int, unsigned int, unsigned int):
✓ Branch 0 taken 1743764 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 1743764 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 1743764 times.
✗ Branch 6 not taken.
✗ Branch 8 not taken.
✓ Branch 9 taken 1743764 times.
✗ Branch 10 not taken.
✓ Branch 11 taken 1743764 times.
 1746424 if (!x || !y || x >= row() || y >= col()) return;
21
4/4
tifa_libs::fenwick2d<int>::add(unsigned int, unsigned int, int):
✓ Branch 2 taken 7218 times.
✓ Branch 3 taken 2660 times.
tifa_libs::fenwick2d<unsigned int>::add(unsigned int, unsigned int, unsigned int):
✓ Branch 2 taken 9729928 times.
✓ Branch 3 taken 1743764 times.
 11483570 for (; x < row(); x += lowbit(x))
22
4/4
tifa_libs::fenwick2d<int>::add(unsigned int, unsigned int, int):
✓ Branch 4 taken 24490 times.
✓ Branch 5 taken 7218 times.
tifa_libs::fenwick2d<unsigned int>::add(unsigned int, unsigned int, unsigned int):
✓ Branch 4 taken 55120281 times.
✓ Branch 5 taken 9729928 times.
 64881917 for (u32 j = y; j < col(); j += lowbit(j)) a[x][j] += v;
23 }
24 //! [xl, xr) * [yl, yr), x > 0, y > 0
25 436606 CEXP void add(u32 xl, u32 yl, u32 xr, u32 yr, cT_(T) v) NE { add(xl, yl, v), add(xl, yr, -v), add(xr, yl, -v), add(xr, yr, v); }
26 //! [1, x) * [1, y), x > 0, y > 0
27 30080684 CEXP T sum(u32 x, u32 y) NE {
28 30080684 T ret = 0;
29
4/4
tifa_libs::fenwick2d<int>::sum(unsigned int, unsigned int):
✓ Branch 3 taken 64857 times.
✓ Branch 4 taken 20654 times.
tifa_libs::fenwick2d<unsigned int>::sum(unsigned int, unsigned int):
✓ Branch 3 taken 148498350 times.
✓ Branch 4 taken 30060030 times.
 178643891 for (x = min(x, row() - 1); x; x -= lowbit(x))
30
4/4
tifa_libs::fenwick2d<int>::sum(unsigned int, unsigned int):
✓ Branch 5 taken 205775 times.
✓ Branch 6 taken 64857 times.
tifa_libs::fenwick2d<unsigned int>::sum(unsigned int, unsigned int):
✓ Branch 5 taken 733590750 times.
✓ Branch 6 taken 148498350 times.
 882359732 for (u32 j = min(y, col() - 1); j; j -= lowbit(j)) ret += a[x][j];
31 30080684 return ret;
32 }
33 //! [xl, xr) * [yl, yr), x > 0, y > 0
34 CEXP T sum(u32 xl, u32 yl, u32 xr, u32 yr) NE {
35 retif_((xl >= xr || yl >= yr) [[unlikely]], 0);
36 return sum(xr, yr) - sum(xl, yr) + sum(xl, yl) - sum(xr, yl);
37 }
38 };
39
40 } // namespace tifa_libs
41