フェニック木（区間加算、区間総和） (lib/binary_tree/fenwick_tree_raq.hpp)

• View this file on GitHub
• Last update: 2026-03-15 18:07:20+09:00
• Include: #include "lib/binary_tree/fenwick_tree_raq.hpp"

Depends on

• フェニック木 (lib/binary_tree/fenwick_tree.hpp)

Verified with

• test/aoj/dsl/raq_rsq.test.cpp
• test/aoj/grl/range_query_on_tree_2.test.cpp

Code

#pragma once
#include "binary_tree/fenwick_tree.hpp"

/// @brief フェニック木（区間加算、区間総和）
template <class T>
struct fenwick_tree_raq {
    fenwick_tree_raq() = default;
    fenwick_tree_raq(int _n) : n(_n), p(n + 1), q(n + 1) {}

    auto operator[](int i) const { return sum(i + 1) - sum(i); }
    auto at(int k) const { return operator[](k); }

    template <class U>
    void build(const std::vector<U> &v) {
        for (int i = 0, n = v.size(); i < n; ++i) add(i, v[i]);
    }

    /// @brief v[k] = val
    void set(int k, T val) { add(k, k + 1, val - at(k)); }
    /// @brief v[k] += val
    void add(int k, T val) { add(k, k + 1, val); }
    /// @brief v[a ... b-1] += val
    void add(int a, int b, T val) {
        assert(0 <= a && a <= b && b <= n);
        p.add(a, -val * a);
        p.add(b, val * b);
        q.add(a, val);
        q.add(b, -val);
    }

    /// @brief v[0] + ... + v[k - 1]
    T sum(int k) const {
        assert(0 <= k && k <= n);
        return p.sum(k) + q.sum(k) * k;
    }
    /// @brief v[a] + ... + v[b - 1]
    T sum(int a, int b) const { return sum(b) - sum(a); }

  private:
    int n;
    fenwick_tree<T> p, q;
};

Traceback (most recent call last):
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/resolver.py", line 291, in resolve
    bundled_code = language.bundle(path, basedir=basedir)
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus.py", line 242, in bundle
    bundler.update(path)
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 479, in update
    self._resolve(pathlib.Path(included), included_from=path)
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 286, in _resolve
    raise BundleErrorAt(path, -1, "no such header")
competitive_verifier.oj.verify.languages.cplusplus_bundle.BundleErrorAt: binary_tree/fenwick_tree.hpp: line -1: no such header

Back to top page