algo/ds/fenwick.h

• View this file on GitHub
• Last update: 2024-12-10 21:37:51-05:00

Depends on

• algo/common.h

Required by

• main.cpp

Verified with

• verify/ds/fenwick.test.cpp

Code

#pragma once
#include "algo/common.h"

namespace algo::ds {

template <typename T>
struct fenwick {
    fenwick(int _n) : n(_n), bit(n, 0) {
    }
    fenwick(const std::vector<T> &a) : fenwick(sz(a)) {
        for (int i = 0; i < n; i++) {
            bit[i] += a[i];
            int r = i | (i + 1);
            if (r < n) bit[r] += bit[i];
        }
    }
    // Inclusive on [l, r]
    T sum(int l, int r) {
        return sum(r) - sum(l - 1);
    }
    T val(int pos) {
        return sum(pos, pos);
    }
    void add(int idx, int delta) {
        for (; idx < n; idx = idx | (idx + 1))
            bit[idx] += delta;
    }
    friend std::ostream &operator<<(std::ostream &os, fenwick f) {
        os << "[";
        bool first = true;
        for (int i = 0; i < f.n; i++) {
            if (!first) os << ", ";
            first = false;
            os << f.val(i);
        }
        os << "]";
        return os;
    }

private:
    int n;
    std::vector<T> bit;
    T sum(int r) {
        T ret(0);
        for (; r >= 0; r = (r & (r + 1)) - 1)
            ret += bit[r];
        return ret;
    }
};

} // namespace algo::ds

#line 2 "algo/common.h"
#ifndef PREPROCESS
#include <bits/stdc++.h>
#endif

namespace algo {}

#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#line 3 "algo/ds/fenwick.h"

namespace algo::ds {

template <typename T>
struct fenwick {
    fenwick(int _n) : n(_n), bit(n, 0) {
    }
    fenwick(const std::vector<T> &a) : fenwick(sz(a)) {
        for (int i = 0; i < n; i++) {
            bit[i] += a[i];
            int r = i | (i + 1);
            if (r < n) bit[r] += bit[i];
        }
    }
    // Inclusive on [l, r]
    T sum(int l, int r) {
        return sum(r) - sum(l - 1);
    }
    T val(int pos) {
        return sum(pos, pos);
    }
    void add(int idx, int delta) {
        for (; idx < n; idx = idx | (idx + 1))
            bit[idx] += delta;
    }
    friend std::ostream &operator<<(std::ostream &os, fenwick f) {
        os << "[";
        bool first = true;
        for (int i = 0; i < f.n; i++) {
            if (!first) os << ", ";
            first = false;
            os << f.val(i);
        }
        os << "]";
        return os;
    }

private:
    int n;
    std::vector<T> bit;
    T sum(int r) {
        T ret(0);
        for (; r >= 0; r = (r & (r + 1)) - 1)
            ret += bit[r];
        return ret;
    }
};

} // namespace algo::ds

Back to top page