The implementation of Fenwick tree.

fenwick.hpp

#pragma once

#include <vector>

class Fenwick {
    std::vector<size_t> data;

    size_t parent(size_t i) const {
        return i - (i & (-i));
    }

    size_t next(size_t i) const {
        return i + (i & (-i));
    }

public:
    Fenwick(size_t len) : data(len + 1, 0) {}

    size_t sum_to(size_t i) const {
        ++i;
        size_t sum = 0;
        while (0 < i) {
            sum += data.at(i);
            i = parent(i);
        }
        return sum;
    }

    void add(size_t i, size_t val) {
        ++i;
        while (i < data.size()) {
            data[i] += val;
            i = next(i);
        }
    }
};