データ構造/Fenwick tree/区間加算クエリ対応 Fenwick tree
(test/data_structure/fenwick_tree/fenwick_tree_supporting_range_add_query.test.cpp)

• View this file on GitHub
• Last update: 2023-02-25 16:35:06+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_G

Depends on

• 区間加算クエリ対応 Fenwick tree (include/emthrm/data_structure/fenwick_tree/fenwick_tree_supporting_range_add_query.hpp)

Code

/*
 * @title データ構造/Fenwick tree/区間加算クエリ対応 Fenwick tree
 *
 * verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_G
 */

#include <iostream>

#include "emthrm/data_structure/fenwick_tree/fenwick_tree_supporting_range_add_query.hpp"

int main() {
  int n, q;
  std::cin >> n >> q;
  emthrm::FenwickTreeSupportingRangeAddQuery<long long> bit(n);
  while (q--) {
    int kind, s, t;
    std::cin >> kind >> s >> t;
    --s; --t;
    if (kind == 0) {
      int x;
      std::cin >> x;
      bit.add(s, t + 1, x);
    } else if (kind == 1) {
      std::cout << bit.sum(s, t + 1) << '\n';
    }
  }
  return 0;
}

#line 1 "test/data_structure/fenwick_tree/fenwick_tree_supporting_range_add_query.test.cpp"
/*
 * @title データ構造/Fenwick tree/区間加算クエリ対応 Fenwick tree
 *
 * verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_G
 */

#include <iostream>

#line 1 "include/emthrm/data_structure/fenwick_tree/fenwick_tree_supporting_range_add_query.hpp"



#include <vector>

namespace emthrm {

template <typename Abelian>
struct FenwickTreeSupportingRangeAddQuery {
  explicit FenwickTreeSupportingRangeAddQuery(
      const int n_, const Abelian ID = 0)
      : n(n_ + 1), ID(ID) {
    data_const.assign(n, ID);
    data_linear.assign(n, ID);
  }

  void add(int left, const int right, const Abelian val) {
    if (right < ++left) [[unlikely]] return;
    for (int i = left; i < n; i += i & -i) {
      data_const[i] -= val * (left - 1);
      data_linear[i] += val;
    }
    for (int i = right + 1; i < n; i += i & -i) {
      data_const[i] += val * right;
      data_linear[i] -= val;
    }
  }

  Abelian sum(const int idx) const {
    Abelian res = ID;
    for (int i = idx; i > 0; i -= i & -i) {
      res += data_linear[i];
    }
    res *= idx;
    for (int i = idx; i > 0; i -= i & -i) {
      res += data_const[i];
    }
    return res;
  }

  Abelian sum(const int left, const int right) const {
    return left < right ? sum(right) - sum(left) : ID;
  }

  Abelian operator[](const int idx) const { return sum(idx, idx + 1); }

 private:
  const int n;
  const Abelian ID;
  std::vector<Abelian> data_const, data_linear;
};

}  // namespace emthrm


#line 10 "test/data_structure/fenwick_tree/fenwick_tree_supporting_range_add_query.test.cpp"

int main() {
  int n, q;
  std::cin >> n >> q;
  emthrm::FenwickTreeSupportingRangeAddQuery<long long> bit(n);
  while (q--) {
    int kind, s, t;
    std::cin >> kind >> s >> t;
    --s; --t;
    if (kind == 0) {
      int x;
      std::cin >> x;
      bit.add(s, t + 1, x);
    } else if (kind == 1) {
      std::cout << bit.sum(s, t + 1) << '\n';
    }
  }
  return 0;
}

Back to top page