Dual-Segment-Tree
(segtree/dual-segment-tree.cpp)

• View this file on GitHub
• Last update: 2021-04-09 16:57:09+09:00

説明

双対セグ木

区間更新と一点取得が可能

計算量

• 初期化: $O(n)$
• クエリ: $O(\log n)$

Verified with

• test/AOJ-DLS-2-D.test.cpp

Code

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

template <class S, class F, S (*mapping)(F, S), F (*composition)(F, F),
          F (*id)()>
class DualSegmentTree {
    int _n, sz, lg;
    vector<S> data;
    vector<F> lazy;

    void _push(int k, F f) {
        if(k < sz)
            lazy[k] = composition(f, lazy[k]);
        else
            data[k - sz] = mapping(f, data[k - sz]);
    }
    void push(int k) {
        _push(k << 1, lazy[k]);
        _push(k << 1 | 1, lazy[k]);
        lazy[k] = id();
    }

public:
    DualSegmentTree() = default;
    explicit DualSegmentTree(const vector<S>& v) : _n(v.size()) {
        lg = 0;
        while(1U << lg < (uint)_n) lg++;
        sz = 1 << lg;
        data = v;
        data.resize(sz);
        lazy.assign(sz, id());
    }

    void set(int p, S x) {
        assert(0 <= p && p < _n);
        p += sz;
        for(int i = lg; i >= 1; i--) push(p >> i);
        data[p - sz] = x;
    }

    S get(int p) {
        assert(0 <= p && p < _n);
        p += sz;
        for(int i = lg; i >= 1; i--) push(p >> i);
        return data[p - sz];
    }

    void apply(int p, F f) {
        assert(0 <= p && p < _n);
        p += sz;
        for(int i = lg; i >= 1; i--) push(p >> i);
        data[p - sz] = mapping(f, data[p]);
    }
    void apply(int l, int r, F f) {
        assert(0 <= l && l <= r && r <= _n);
        if(l == r) return;
        l += sz;
        r += sz;

        for(int i = lg; i >= 1; i--) {
            if(((l >> i) << i) != l) push(l >> i);
            if(((r >> i) << i) != r) push((r - 1) >> i);
        }

        while(l < r) {
            if(l & 1) _push(l++, f);
            if(r & 1) _push(--r, f);
            l >>= 1;
            r >>= 1;
        }
    }
};
/*
 * @brief Dual-Segment-Tree
 * @docs docs/dual-segment-tree.md
 */

#line 2 "segtree/dual-segment-tree.cpp"
#include <bits/stdc++.h>
using namespace std;

template <class S, class F, S (*mapping)(F, S), F (*composition)(F, F),
          F (*id)()>
class DualSegmentTree {
    int _n, sz, lg;
    vector<S> data;
    vector<F> lazy;

    void _push(int k, F f) {
        if(k < sz)
            lazy[k] = composition(f, lazy[k]);
        else
            data[k - sz] = mapping(f, data[k - sz]);
    }
    void push(int k) {
        _push(k << 1, lazy[k]);
        _push(k << 1 | 1, lazy[k]);
        lazy[k] = id();
    }

public:
    DualSegmentTree() = default;
    explicit DualSegmentTree(const vector<S>& v) : _n(v.size()) {
        lg = 0;
        while(1U << lg < (uint)_n) lg++;
        sz = 1 << lg;
        data = v;
        data.resize(sz);
        lazy.assign(sz, id());
    }

    void set(int p, S x) {
        assert(0 <= p && p < _n);
        p += sz;
        for(int i = lg; i >= 1; i--) push(p >> i);
        data[p - sz] = x;
    }

    S get(int p) {
        assert(0 <= p && p < _n);
        p += sz;
        for(int i = lg; i >= 1; i--) push(p >> i);
        return data[p - sz];
    }

    void apply(int p, F f) {
        assert(0 <= p && p < _n);
        p += sz;
        for(int i = lg; i >= 1; i--) push(p >> i);
        data[p - sz] = mapping(f, data[p]);
    }
    void apply(int l, int r, F f) {
        assert(0 <= l && l <= r && r <= _n);
        if(l == r) return;
        l += sz;
        r += sz;

        for(int i = lg; i >= 1; i--) {
            if(((l >> i) << i) != l) push(l >> i);
            if(((r >> i) << i) != r) push((r - 1) >> i);
        }

        while(l < r) {
            if(l & 1) _push(l++, f);
            if(r & 1) _push(--r, f);
            l >>= 1;
            r >>= 1;
        }
    }
};
/*
 * @brief Dual-Segment-Tree
 * @docs docs/dual-segment-tree.md
 */

Back to top page