unabstracted_libs/segment-tree/aoj-dsl-2-b(RSQ).test.cpp

• View this file on GitHub
• Last update: 2024-08-21 21:41:37+09:00
• Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_B

Depends on

• template/template.hpp

Code

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_B"

#include "template/template.hpp"
#include <vector>

vector<ll> dat;
int sz;

// k番目(0-indexed)の値にaを加算
void update(int k, int a) {
  k += sz;
  dat[k] += a;
  while (k > 0) {
    k /= 2;
    dat[k] = dat[k * 2] + dat[k * 2 + 1];
  }
}

// [l, r)の和を求める(l, rは0-indexed)
ll query(int l, int r) {

  l += sz; r += sz;
  assert(0<=l && 0<= r && l <= r);
  int L = 0, R = 0;
  while (l < r) {
    if (l % 2 == 1) {
      L = L + dat[l];
      l++;
    }

    if (r % 2 == 1) {
      r--;
      R = dat[r] + R;
    }

    l /= 2; r /= 2;
  }
  return L + R;
}


int main() {
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  int n, q; cin >> n >> q;

  sz = 1; while (sz < n) sz *= 2;

  dat.resize(sz * 2, 0);

  while (q--) {
    int com, x, y; cin >> com >> x >> y;
    x--;
    if (com == 0) {
      update(x, y);
    }
    else {
      cout << query(x, y) << endl;
    }
  }
  return 0;
}

#line 1 "unabstracted_libs/segment-tree/aoj-dsl-2-b(RSQ).test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_B"

#line 1 "template/template.hpp"
#include <iostream>
#include <cassert>
using namespace std;
using ll = long long;
template<class T> inline bool chmax(T& a, const T& b) {if (a<b) {a=b; return true;} return false;}
template<class T> inline bool chmin(T& a, const T& b) {if (b<a) {a=b; return true;} return false;}
const int INTINF = 1000001000;
const int INTMAX = 2147483647;
const ll LLMAX = 9223372036854775807;
const ll LLINF = 1000000000000000000;
#line 4 "unabstracted_libs/segment-tree/aoj-dsl-2-b(RSQ).test.cpp"
#include <vector>

vector<ll> dat;
int sz;

// k番目(0-indexed)の値にaを加算
void update(int k, int a) {
  k += sz;
  dat[k] += a;
  while (k > 0) {
    k /= 2;
    dat[k] = dat[k * 2] + dat[k * 2 + 1];
  }
}

// [l, r)の和を求める(l, rは0-indexed)
ll query(int l, int r) {

  l += sz; r += sz;
  assert(0<=l && 0<= r && l <= r);
  int L = 0, R = 0;
  while (l < r) {
    if (l % 2 == 1) {
      L = L + dat[l];
      l++;
    }

    if (r % 2 == 1) {
      r--;
      R = dat[r] + R;
    }

    l /= 2; r /= 2;
  }
  return L + R;
}


int main() {
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  int n, q; cin >> n >> q;

  sz = 1; while (sz < n) sz *= 2;

  dat.resize(sz * 2, 0);

  while (q--) {
    int com, x, y; cin >> com >> x >> y;
    x--;
    if (com == 0) {
      update(x, y);
    }
    else {
      cout << query(x, y) << endl;
    }
  }
  return 0;
}

Back to top page