verify/ds/fenwick.test.cpp

• View this file on GitHub
• Last update: 2026-07-26 15:26:45-04:00
• Problem: https://judge.yosupo.jp/problem/point_add_range_sum

Depends on

• algo/common.h
• algo/ds/fenwick.h

Code

#define PROBLEM "https://judge.yosupo.jp/problem/point_add_range_sum"
#include "algo/common.h"

/* #include */
#include "algo/ds/fenwick.h"

using namespace std;
using namespace algo;
using ds::fenwick;

void solve() {
    int n, q;
    cin >> n >> q;
    vector<int64_t> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    fenwick<int64_t> t(a);
    for (int i = 0; i < q; i++) {
        int typ, x, y;
        cin >> typ >> x >> y;
        if (typ == 0) {
            t.add(x, y);
        } else {
            cout << t.sum(x, y - 1) << '\n';
        }
    }
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    // int t;
    // cin >> t;
    // while (t--)
    solve();
}

#line 1 "verify/ds/fenwick.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/point_add_range_sum"
#line 2 "algo/common.h"
#ifndef PREPROCESS
#include <bits/stdc++.h>
#include <cassert>
#endif

namespace algo {

// Indices and sizes into library containers. Signed, so the usual "walk down to
// -1" loops still terminate; widening the whole library is a change here alone.
using index_t = int;

} // namespace algo
#line 3 "verify/ds/fenwick.test.cpp"

/* #include */
#line 3 "algo/ds/fenwick.h"

namespace algo::ds {

template <typename T>
struct fenwick {
    fenwick(index_t _n) : n(_n), bit(n, 0) {
    }
    fenwick(const std::vector<T> &a) : fenwick((index_t)a.size()) {
        for (index_t i = 0; i < n; i++) {
            bit[i] += a[i];
            index_t r = i | (i + 1);
            if (r < n) bit[r] += bit[i];
        }
    }
    // Inclusive on [l, r]
    T sum(index_t l, index_t r) {
        return sum(r) - sum(l - 1);
    }
    T val(index_t pos) {
        return sum(pos, pos);
    }
    void add(index_t idx, T delta) {
        for (; idx < n; idx = idx | (idx + 1))
            bit[idx] += delta;
    }
    friend std::ostream &operator<<(std::ostream &os, fenwick f) {
        os << "[";
        bool first = true;
        for (index_t i = 0; i < f.n; i++) {
            if (!first) os << ", ";
            first = false;
            os << f.val(i);
        }
        os << "]";
        return os;
    }

private:
    index_t n;
    std::vector<T> bit;
    T sum(index_t r) {
        T ret(0);
        for (; r >= 0; r = (r & (r + 1)) - 1)
            ret += bit[r];
        return ret;
    }
};

} // namespace algo::ds
#line 6 "verify/ds/fenwick.test.cpp"

using namespace std;
using namespace algo;
using ds::fenwick;

void solve() {
    int n, q;
    cin >> n >> q;
    vector<int64_t> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    fenwick<int64_t> t(a);
    for (int i = 0; i < q; i++) {
        int typ, x, y;
        cin >> typ >> x >> y;
        if (typ == 0) {
            t.add(x, y);
        } else {
            cout << t.sum(x, y - 1) << '\n';
        }
    }
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    // int t;
    // cin >> t;
    // while (t--)
    solve();
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	example_00	AC	3 ms	4 MB
g++	max_random_00	AC	141 ms	11 MB
g++	max_random_01	AC	140 ms	11 MB
g++	max_random_02	AC	140 ms	11 MB
g++	max_random_03	AC	140 ms	11 MB
g++	max_random_04	AC	143 ms	11 MB
g++	random_00	AC	138 ms	9 MB
g++	random_01	AC	122 ms	11 MB
g++	random_02	AC	81 ms	4 MB
g++	random_03	AC	33 ms	10 MB
g++	random_04	AC	40 ms	8 MB
g++	small_00	AC	3 ms	4 MB
g++	small_01	AC	3 ms	4 MB
g++	small_02	AC	2 ms	4 MB
g++	small_03	AC	2 ms	4 MB
g++	small_04	AC	2 ms	4 MB
g++	small_05	AC	2 ms	4 MB
g++	small_06	AC	2 ms	4 MB
g++	small_07	AC	2 ms	4 MB
g++	small_08	AC	2 ms	4 MB
g++	small_09	AC	2 ms	4 MB

Back to top page