Test/AOJ/SegmentTree-RangeSumQuery.test.cpp

View this file on GitHub
Last update: 2021-11-21 13:46:02+09:00
Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/2/DSL_2_B

Depends on

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/2/DSL_2_B"

#include<bits/stdc++.h>
using namespace std;

#include"../../Other/Template.cpp"
#include"../../DataStructure/SegmentTree.cpp"

int main() {
    int N,Q;
    cin >> N >> Q;
    SegmentTree<int> seg(N,0,
    [](int a,int b){return a + b;},
    [](int a,int b){return a + b;});
    for(int i = 0;i < Q;i++) {
        int t;
        cin >> t;
        if(t == 0) {
            int p,x;
            cin >> p >> x;
            p--;
            seg.set_val(p,x);
        }
        else {
            int s,t;
            cin >> s >> t;
            s--;
            t--;
            cout << seg.fold(s,t + 1) << endl;
        }
    }
}

#line 1 "Test/AOJ/SegmentTree-RangeSumQuery.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/2/DSL_2_B"

#include<bits/stdc++.h>
using namespace std;

#line 1 "Other/Template.cpp"
constexpr int Inf = 2000000030;
constexpr long long INF= 2000000000000000000;

template<typename T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; }
template<typename T> inline bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; }
#line 1 "DataStructure/SegmentTree.cpp"
template<typename T>
class SegmentTree {
    int internal_size, seg_size;
    const T def;
    std::vector<T> dat;
    std::function<T(T, T)> operation;
    std::function<T(T, T)> update;

public:
    explicit SegmentTree(const int size, const T& e, std::function<T(T, T)> operation, std::function<T(T, T)> update): internal_size(size), def(e), operation(operation), update(update) {
        for(seg_size = 1; seg_size < internal_size; seg_size *= 2);
        dat = std::vector<T>(2 * seg_size, def);
    }

    explicit SegmentTree(std::vector<T> v, const T& e,std::function<T(T, T)> operation, std::function<T(T, T)> update): internal_size(v.size()), def(e), operation(operation), update(update) {
        for(seg_size = 1; seg_size < internal_size; seg_size *= 2);
        dat.resize(2 * seg_size, def);

        for(int i = 0; i < seg_size;i++) dat[i + seg_size] = v[i];
        for(int i = seg_size - 1; i >= 1; i--) {
            dat[i] = operation(dat[i * 2], dat[i * 2 + 1]);
        }
    }

    void set_val(int i, const T& value) {
        i += seg_size;
        dat[i] = update(dat[i], value);
        while(i > 1) {
            i >>= 1;
            dat[i] = operation(dat[i * 2], dat[i * 2 + 1]);
        }
    }

    T fold(int l,int r) {
        l += seg_size;
        r += seg_size;
        T ret = def;
        while(l < r) {
            if(l & 1) ret = operation(ret,dat[l++]);
            if(r & 1) ret = operation(dat[--r],ret);
            l >>= 1;
            r >>= 1;
        }
        return ret;
    }

    int max_right(int l, std::function<bool(T)> f) {
        if(l == internal_size) return internal_size;
        l += seg_size;
        T sum = def;
        do {
            while(!(l & 1)) l >>= 1;
            if(!f(operation(sum, dat[l]))) {
                while(l < seg_size) {
                    l <<= 1;
                    if(f(operation(sum, dat[l]))) sum = operation(sum, dat[l++]);
                }
                return l - seg_size;
            }
        } while((l & -1) != l);
        return internal_size;
    }

    T operator[](int i) {return dat[i + seg_size];}
};
#line 8 "Test/AOJ/SegmentTree-RangeSumQuery.test.cpp"

int main() {
    int N,Q;
    cin >> N >> Q;
    SegmentTree<int> seg(N,0,
    [](int a,int b){return a + b;},
    [](int a,int b){return a + b;});
    for(int i = 0;i < Q;i++) {
        int t;
        cin >> t;
        if(t == 0) {
            int p,x;
            cin >> p >> x;
            p--;
            seg.set_val(p,x);
        }
        else {
            int s,t;
            cin >> s >> t;
            s--;
            t--;
            cout << seg.fold(s,t + 1) << endl;
        }
    }
}