src/test/yosupo_point_add_range_sum.cpp

View this file on GitHub
Last update: 2025-10-07 04:08:36+09:00
Problem: https://judge.yosupo.jp/problem/point_add_range_sum

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/point_add_range_sum"
#include "../dynamic_segtree.hpp"

long op(long l, long r) { return l + r; }
long e() { return 0; }

int main() {
    int n, q;
    cin >> n >> q;
    dynamic_segtree<long, op, e> seg(n);
    rep(i, n) {
        int a;
        cin >> a;
        seg.set(i, a);
    }
    rep(i, q) {
        int c, x, y;
        cin >> c >> x >> y;
        if(c == 0) {
            seg.set(x, seg.get(x) + y);
        }
        else {
            cout << seg.prod(x, y) << "\n";
        }
    }
}

#line 1 "src/test/yosupo_point_add_range_sum.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/point_add_range_sum"
#line 2 "src/template.hpp"
#include <bits/stdc++.h>
using namespace std;
#define si(a) (long)a.size()
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define rep(i, n) for(long i = 0; i < (long)(n); ++i)
template<typename T> bool chmin(T& a, T b) { return b < a ? (a = b, 1) : 0; }
template<typename T> bool chmax(T& a, T b) { return b > a ? (a = b, 1) : 0; }
struct _ {
    _() { cin.tie(0)->sync_with_stdio(0), cout.tie(0), cout << fixed << setprecision(16); }
} __;
#line 3 "src/dynamic_segtree.hpp"

//省メモリ化はしてません
template<class S, S (*op)(S, S), S (*e)(), typename K = uint64_t> struct dynamic_segtree {
    struct Node {
        Node *p, *left, *right;
        S d;
        Node(Node* _p = nullptr): p(_p), left(nullptr), right(nullptr), d(e()) {}
    };

    K n, log;
    Node* root;
    dynamic_segtree(K _n) {
        n = __bit_ceil(_n);
        log = __countr_zero(n);
        root = new Node();
    }
    void set(K p, S x) {
        Node* now = root;
        for(int i = log; i--;) {
            if(p >> i & 1) {
                if(!now->right) now->right = new Node(now);
                now = now->right;
            }
            else {
                if(!now->left) now->left = new Node(now);
                now = now->left;
            }
        }
        now->d = x;
        while(now->p) {
            now = now->p;
            now->d = op(now->left ? now->left->d : e(), now->right ? now->right->d : e());
        }
    }

    S get(K p) {
        Node* now = root;
        for(int i = log; i--;) {
            if(p >> i & 1) {
                if(!now->right) return e();
                now = now->right;
            }
            else {
                if(!now->left) return e();
                now = now->left;
            }
        }
        return now->d;
    }
    S prod(K l, K r) { return prod(l, r, root, 0, n); }

    S prod(K a, K b, Node*& now, K l, K r) {
        if(!now || r <= a || b <= l) return e();
        if(a <= l && r <= b) return now->d;
        K c = (l + r) >> 1;
        S lv = prod(a, b, now->left, l, c);
        S rv = prod(a, b, now->right, c, r);
        return op(lv, rv);
    }
};

template<class T> using DynamicSegtreeFrom =
    dynamic_segtree<class T::S, T::op, T::e, typename T::K>;
#line 3 "src/test/yosupo_point_add_range_sum.cpp"

long op(long l, long r) { return l + r; }
long e() { return 0; }

int main() {
    int n, q;
    cin >> n >> q;
    dynamic_segtree<long, op, e> seg(n);
    rep(i, n) {
        int a;
        cin >> a;
        seg.set(i, a);
    }
    rep(i, q) {
        int c, x, y;
        cin >> c >> x >> y;
        if(c == 0) {
            seg.set(x, seg.get(x) + y);
        }
        else {
            cout << seg.prod(x, y) << "\n";
        }
    }
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	example_00	AC	5 ms	4 MB
g++	max_random_00	AC	460 ms	51 MB
g++	max_random_01	AC	465 ms	51 MB
g++	max_random_02	AC	460 ms	51 MB
g++	max_random_03	AC	458 ms	51 MB
g++	max_random_04	AC	461 ms	51 MB
g++	random_00	AC	338 ms	40 MB
g++	random_01	AC	389 ms	47 MB
g++	random_02	AC	159 ms	9 MB
g++	random_03	AC	119 ms	44 MB
g++	random_04	AC	120 ms	30 MB
g++	small_00	AC	5 ms	4 MB
g++	small_01	AC	4 ms	4 MB
g++	small_02	AC	4 ms	4 MB
g++	small_03	AC	4 ms	4 MB
g++	small_04	AC	4 ms	4 MB
g++	small_05	AC	4 ms	4 MB
g++	small_06	AC	4 ms	4 MB
g++	small_07	AC	4 ms	4 MB
g++	small_08	AC	4 ms	4 MB
g++	small_09	AC	4 ms	4 MB
clang++	example_00	AC	5 ms	4 MB
clang++	max_random_00	AC	476 ms	51 MB
clang++	max_random_01	AC	468 ms	51 MB
clang++	max_random_02	AC	446 ms	51 MB
clang++	max_random_03	AC	476 ms	50 MB
clang++	max_random_04	AC	459 ms	51 MB
clang++	random_00	AC	351 ms	40 MB
clang++	random_01	AC	390 ms	47 MB
clang++	random_02	AC	165 ms	9 MB
clang++	random_03	AC	123 ms	44 MB
clang++	random_04	AC	128 ms	30 MB
clang++	small_00	AC	5 ms	4 MB
clang++	small_01	AC	5 ms	4 MB
clang++	small_02	AC	5 ms	4 MB
clang++	small_03	AC	5 ms	4 MB
clang++	small_04	AC	4 ms	4 MB
clang++	small_05	AC	5 ms	4 MB
clang++	small_06	AC	5 ms	4 MB
clang++	small_07	AC	5 ms	4 MB
clang++	small_08	AC	4 ms	4 MB
clang++	small_09	AC	4 ms	4 MB