セグメント木 (一点加算・区間和)
(test/aoj/DSL_2_B.segtree.test.cpp)

• View this file on GitHub
• Last update: 2021-04-15 20:24:09+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_B

Depends on

• セグメント木 (一点更新、区間取得) (datastructure/segment-tree.hpp)
• monoid/add.hpp

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_B"
// @title セグメント木 (一点加算・区間和)

#include "../../monoid/add.hpp"
#include "../../datastructure/segment-tree.hpp"

#include <iostream>
using namespace std;

int main() {
  int n, q; cin >> n >> q;
  SegmentTree<monoid::add<int>> st(n);
  for (int i = 0; i < q; ++i) {
    int c, x, y; cin >> c >> x >> y; --x;
    if (c == 0) st.update(x, st[x]+y);
    else cout << st.query(x, y) << endl;
  }
}

#line 1 "test/aoj/DSL_2_B.segtree.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_B"
// @title セグメント木 (一点加算・区間和)

#line 1 "monoid/add.hpp"



namespace monoid {
template <class T>
struct add {
  typedef T value_t;
  T identity() const { return T(); }
  T merge(T a, T b) const { return a+b; }
};
} // namespace monoid


#line 1 "datastructure/segment-tree.hpp"


/**
 * @title セグメント木 (一点更新、区間取得)
 * 
 */
#include <cassert>
#include <vector>

template <class Monoid>
struct SegmentTree {
  typedef typename Monoid::value_t value_t;
  const Monoid monoid;
  int n; // n_以上の最小の2冪
  std::vector<value_t> data;
  SegmentTree(int n_): monoid() {
    n = 1;
    while (n < n_) n *= 2;
    data.assign(2*n-1, monoid.identity());
  }

  // k番目の値(0-indexed)をaに変更
  void update(int k, int a) { // 0-indexed
    assert(0 <= k && k < n);
    // 葉の節点
    data[k+n-1] = a;
    // 登りながら更新
    for (k = (k+n)/2; k > 0; k /= 2) {  // 1-indexed
      data[k-1] = monoid.merge(data[2*k-1], data[2*k]);
    }
  }

  value_t query(int l, int r) {  // 0-indexed, [l, r)
    assert(0 <= l && l <= r && r <= n);
    value_t vl = monoid.identity(), vr = monoid.identity();
    for (l += n, r += n; l < r; l /= 2, r /= 2) {  // 1-indexed
      if (l & 1) vl = monoid.merge(vl, data[(l++)-1]);
      if (r & 1) vr = monoid.merge(data[(--r)-1],vr);
    }
    return monoid.merge(vl, vr);
  }

  value_t operator[](const int &k) {
    return query(k, k + 1);
  }
};


#line 6 "test/aoj/DSL_2_B.segtree.test.cpp"

#include <iostream>
using namespace std;

int main() {
  int n, q; cin >> n >> q;
  SegmentTree<monoid::add<int>> st(n);
  for (int i = 0; i < q; ++i) {
    int c, x, y; cin >> c >> x >> y; --x;
    if (c == 0) st.update(x, st[x]+y);
    else cout << st.query(x, y) << endl;
  }
}

Back to top page