data-structure/range-BIT.hpp

• View this file on GitHub
• Last update: 2023-10-30 20:10:44+09:00
• Include: #include "data-structure/range-BIT.hpp"

Depends on

• data-structure/BIT.hpp

Code

#pragma once

#include "BIT.hpp"

template <typename T> class RangeBIT {
  public:
    RangeBIT() = default;
    explicit RangeBIT(int N) : bt1(N + 1), bt2(N + 1){};
    void add(int l, int r, T val) {
        bt1.add(l, -val * l);
        bt1.add(r, val * r);
        bt2.add(l, val);
        bt2.add(r, -val);
    }
    void add(int pos, T val) { add(pos, pos + 1, val); }
    T sum(int r) { return bt1.sum(r) + bt2.sum(r) * r; }
    T sum(int l, int r) {
        assert(l <= r);
        if(l == r) return T(0);
        return (sum(r) - sum(l));
    }

  private:
    BIT<T> bt1, bt2;
};

#line 2 "data-structure/range-BIT.hpp"

#line 2 "data-structure/BIT.hpp"

#include <cassert>
#include <vector>

template <typename T> class BIT {
  public:
    BIT() = default;
    explicit BIT(int N) : N(N), dat(N + 1, 0) {}
    T sum(int r) {
        T ret = 0;
        for(; r >= 1; r -= lsb(r)) ret += dat[r];
        return ret;
    }
    T sum(int l, int r) {
        assert(l <= r);
        if(l == r) return T(0);
        return (sum(r) - sum(l));
    }
    void add(int pos, T val) {
        for(int i = pos + 1; i <= N; i += lsb(i)) dat[i] += val;
    }
    int lower_bound(T val) {
        int pos = 0;
        int k = 1;
        while(2 * k <= N) k <<= 1;
        for(; k >= 1; k >>= 1) {
            if(pos + k <= N and dat[pos + k] < val) {
                pos += k;
                val -= dat[pos];
            }
        }
        return pos + 1;
    }

  private:
    int N;
    std::vector<T> dat;

    inline int lsb(int i) { return i & (-i); }
};
#line 4 "data-structure/range-BIT.hpp"

template <typename T> class RangeBIT {
  public:
    RangeBIT() = default;
    explicit RangeBIT(int N) : bt1(N + 1), bt2(N + 1){};
    void add(int l, int r, T val) {
        bt1.add(l, -val * l);
        bt1.add(r, val * r);
        bt2.add(l, val);
        bt2.add(r, -val);
    }
    void add(int pos, T val) { add(pos, pos + 1, val); }
    T sum(int r) { return bt1.sum(r) + bt2.sum(r) * r; }
    T sum(int l, int r) {
        assert(l <= r);
        if(l == r) return T(0);
        return (sum(r) - sum(l));
    }

  private:
    BIT<T> bt1, bt2;
};

Back to top page