1
struct FwTree {
2
    vector<ll> bit;
3
    int n;
4

5
    FwTree(int n) : n(n), bit(n + 1, 0) {}
6

7
    FwTree(const vector<int>& a) : FwTree(a.size()) {
8
        for (int i = 1; i <= n; i++)
9
            bit[i] = a[i - 1];
10
        for (int i = 1; i <= n; i++) {
11
            int pa = i + (i & -i);
12
            if (pa <= n)
13
                bit[pa] += bit[i];
14
        }
15
    }
16

17
    inline int lowbit(int x) {
18
        return x & (-x);
19
    }
20

21
    void add(int x, ll val) {
22
        for (++x; x <= n; x += lowbit(x))
23
            bit[x] += val;
24
    }
25

26
    ll sum(int x) {
27
        ll ret = 0;
28
        for (++x; x > 0; x -= lowbit(x))
29
            ret += bit[x];
30
        return ret;
31
    }
32

33
    ll sum(int l, int r) {
34
        if (l > r) return 0;
35
        return sum(r) - sum(l - 1);
36
    }
37
};