Fenwick Tree with Range Update
(data-structure/range_fenwick_tree.hpp)

• View this file on GitHub
• Last update: 2024-01-08 02:22:28+09:00
• Include: #include "data-structure/range_fenwick_tree.hpp"

Description

接頭辞和を扱う Fenwick tree を2つ使うことで，区間加算を実現できる．

空間計算量: $O(n)$

Operations

• RangeFenwickTree(int n)
  • サイズnで要素がすべて $0$ の区間更新 Fenwick tree を構築する
  • 時間計算量: $O(n)$
• T prefix_sum(int i)
  • $[0, i)$ の総和を計算する
  • 時間計算量: $O(\log n)$
• void add(int l, int r, T x)
  • 区間 $[l, r)$ に $x$ を加える
  • 時間計算量: $O(\log n)$

Reference

• Binary Indexed Tree のはなし

Verified with

• test/aoj/DSL_2_G.range_fenwick_tree.test.cpp

Code

#pragma once
#include <vector>

template <typename T>
class RangeFenwickTree {
   public:
    RangeFenwickTree() = default;
    explicit RangeFenwickTree(int n) : n(n), data0(n + 1), data1(n + 1) {}

    T prefix_sum(int i) const {
        return prefix_sum(data0, i) * (i - 1) + prefix_sum(data1, i);
    }

    void add(int l, int r, T x) {
        add(data0, l, x);
        add(data0, r, -x);
        add(data1, l, -x * (l - 1));
        add(data1, r, x * (r - 1));
    }

   private:
    int n;
    std::vector<T> data0, data1;

    T prefix_sum(const std::vector<T>& data, int i) const {
        T ret = 0;
        for (; i > 0; i -= i & -i) ret += data[i];
        return ret;
    }

    void add(std::vector<T>& data, int i, T x) {
        for (++i; i <= n; i += i & -i) data[i] += x;
    }
};

#line 2 "data-structure/range_fenwick_tree.hpp"
#include <vector>

template <typename T>
class RangeFenwickTree {
   public:
    RangeFenwickTree() = default;
    explicit RangeFenwickTree(int n) : n(n), data0(n + 1), data1(n + 1) {}

    T prefix_sum(int i) const {
        return prefix_sum(data0, i) * (i - 1) + prefix_sum(data1, i);
    }

    void add(int l, int r, T x) {
        add(data0, l, x);
        add(data0, r, -x);
        add(data1, l, -x * (l - 1));
        add(data1, r, x * (r - 1));
    }

   private:
    int n;
    std::vector<T> data0, data1;

    T prefix_sum(const std::vector<T>& data, int i) const {
        T ret = 0;
        for (; i > 0; i -= i & -i) ret += data[i];
        return ret;
    }

    void add(std::vector<T>& data, int i, T x) {
        for (++i; i <= n; i += i & -i) data[i] += x;
    }
};

Back to top page