1. hotman78

    No comment

    hotman78
Changes in body
Source | HTML | Preview

ごめんなさい

可換性を必要とします
f(s,node[--r]);をf(node[--r],s);に変えると可換性を要求せずにすむらしいです(凄い)

気持ち

IMG_20200221_171036.jpg

確かに上手く行きそう

実装

非再帰です

segment.cpp
template<typename T>
struct segment{
    vector<T> node;
    int n;
    segment(int n):n(n){node.assign(n*2+1,e);}
    T get(auto l,auto r){
        l+=n;r+=n;
        T s=e;
        while(l<r){
            if(l&1)f(s,node[l++]);
            if(r&1)f(node[--r],s);
            l/=2;r/=2;
        }
        return s;
    }
    void update(auto t,T x){
        t+=n;
        while(t)f(node[t],x),t/=2;
    }
    T e=0;
    void f(T& s,const T& t){
        s+=t;
    }
};

vertify

Range Sum Query(AOJ)