test/aoj/DSL_2_B.dynamic_segment_tree.test.cpp

• View this file on GitHub
• Last update: 2024-01-07 20:09:47+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_B

Depends on

• Dynamic Segment Tree (data-structure/segtree/dynamic_segment_tree.hpp)

Code

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

#include <bits/stdc++.h>

#include "../../data-structure/segtree/dynamic_segment_tree.hpp"
using namespace std;

struct Monoid {
    using T = int;
    static T id() { return 0; }
    static T op(T a, T b) { return a + b; }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, q;
    cin >> n >> q;
    DynamicSegmentTree<Monoid> st(n);
    for (int i = 0; i < q; ++i) {
        int com, x, y;
        cin >> com >> x >> y;
        if (com == 0)
            st.update(x - 1, st[x - 1] + y);
        else
            cout << st.fold(x - 1, y) << "\n";
    }
}

#line 1 "test/aoj/DSL_2_B.dynamic_segment_tree.test.cpp"
#define PROBLEM \
    "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_B"

#include <bits/stdc++.h>

#line 2 "data-structure/segtree/dynamic_segment_tree.hpp"
#include <bit>
#line 4 "data-structure/segtree/dynamic_segment_tree.hpp"

template <typename M>
class DynamicSegmentTree {
    using T = M::T;

   public:
    DynamicSegmentTree() = default;
    explicit DynamicSegmentTree(long long n)
        : root(std::make_unique<Node>()),
          size(std::bit_ceil((unsigned long long)n)) {}

    T operator[](long long k) const { return fold(k, k + 1); }

    void update(long long k, const T& x) const { update(k, x, root, 0, size); }

    T fold(long long l, long long r) const { return fold(l, r, root, 0, size); }

   private:
    struct Node;
    using node_ptr = std::unique_ptr<Node>;

    struct Node {
        T val;
        node_ptr left, right;
        Node() : val(M::id()), left(nullptr), right(nullptr) {}
    };

    const node_ptr root;
    long long size;

    void update(long long k, const T& x, const node_ptr& n, long long l,
                long long r) const {
        if (r - l == 1) {
            n->val = x;
            return;
        }
        long long m = std::midpoint(l, r);
        if (k < m) {
            if (!n->left) n->left = std::make_unique<Node>();
            update(k, x, n->left, l, m);
            n->val = M::op(n->left->val, n->right ? n->right->val : M::id());
        } else {
            if (!n->right) n->right = std::make_unique<Node>();
            update(k, x, n->right, m, r);
            n->val = M::op(n->left ? n->left->val : M::id(), n->right->val);
        }
    }

    T fold(long long a, long long b, const node_ptr& n, long long l,
           long long r) const {
        if (r <= a || b <= l) return M::id();
        if (a <= l && r <= b) return n->val;
        long long m = std::midpoint(l, r);
        T vl = n->left ? fold(a, b, n->left, l, m) : M::id();
        T vr = n->right ? fold(a, b, n->right, m, r) : M::id();
        return M::op(vl, vr);
    }
};
#line 7 "test/aoj/DSL_2_B.dynamic_segment_tree.test.cpp"
using namespace std;

struct Monoid {
    using T = int;
    static T id() { return 0; }
    static T op(T a, T b) { return a + b; }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, q;
    cin >> n >> q;
    DynamicSegmentTree<Monoid> st(n);
    for (int i = 0; i < q; ++i) {
        int com, x, y;
        cin >> com >> x >> y;
        if (com == 0)
            st.update(x - 1, st[x - 1] + y);
        else
            cout << st.fold(x - 1, y) << "\n";
    }
}

Back to top page