library

This documentation is automatically generated by online-judge-tools/verification-helper

---

Project maintained by tko919 Hosted on GitHub Pages — Theme by mattgraham

2D Binary Indexed Tree
(DataStructure/2dbit.hpp)

• View this file on GitHub
• Last update: 2026-01-30 05:37:33+09:00
• Include: #include "DataStructure/2dbit.hpp"

Depends on

• Binary Indexed Tree (DataStructure/bit.hpp)

Code

#pragma once
#include "DataStructure/bit.hpp"

template <class T> struct BIT2D {
    int n;
    vector<BIT<T>> d;
    vector<int> xs;
    vector<vector<int>> ys;
    vector<pair<ll, ll>> p;
    BIT2D() {}
    void push(ll x, ll y) {
        p.push_back({x, y});
    }
    void init() {
        rep(i, 0, p.size()) xs.push_back(p[i].first);
        sort(ALL(xs));
        xs.erase(unique(ALL(xs)), xs.end());
        n = xs.size() + 1;
        ys.resize(n);
        rep(j, 0, p.size()) {
            int s = upper_bound(ALL(xs), p[j].first) - xs.begin();
            for (int i = s; i < n; i += (i & -i))
                ys[i].push_back(p[j].second);
        }
        d.resize(n);
        rep(i, 0, n) {
            sort(ALL(ys[i]));
            ys[i].erase(unique(ALL(ys[i])), ys[i].end());
            d[i] = BIT<T>(ys[i].size() + 2);
        }
    }
    void add(ll x, ll y, T z = 1) {
        int s = upper_bound(ALL(xs), x) - xs.begin();
        for (int i = s; i < n; i += (i & -i)) {
            int idx = upper_bound(ALL(ys[i]), y) - ys[i].begin();
            d[i].add(idx, z);
        }
    }
    T sum(ll x, ll y) {
        T res = T();
        int s = upper_bound(ALL(xs), x) - xs.begin();
        for (int i = s; i; i -= (i & -i)) {
            int idx = upper_bound(ALL(ys[i]), y) - ys[i].begin();
            res += d[i].sum(idx + 1);
        }
        return res;
    }
    T sum(ll x1, ll y1, ll x2, ll y2) {
        return sum(x2, y2) - sum(x1 - 1, y2) - sum(x2, y1 - 1) +
               sum(x1 - 1, y1 - 1);
    }
};

/**
 * @brief 2D Binary Indexed Tree
 */

#line 2 "DataStructure/bit.hpp"

template <typename T> struct BIT {
    int n;
    T all = T();
    vector<T> val;
    BIT(int _n = 0) : n(_n), val(_n + 10) {}
    void clear() {
        val.assign(n + 10, T());
        all = T();
    }
    void add(int i, T x) {
        for (i++; i <= n; i += (i & -i))
            val[i] = val[i] + x;
        all += x;
    }
    T sum(int i) {
        i = clamp(i, 0, n);
        T res = T();
        for (; i; i -= (i & -i))
            res += val[i];
        return res;
    }
    // [L,R)

    T sum(int L, int R) {
        if (L > R)
            return T();
        return sum(R) - sum(L);
    }
    // max index s.t. sum[0,i]<=x

    int lower_bound(T x) {
        int ret = 0, len = 1;
        while (2 * len <= n)
            len <<= 1;
        for (; len >= 1; len >>= 1) {
            if (ret + len <= n and val[ret + len] < x) {
                ret += len;
                x -= val[ret];
            }
        }
        return ret;
    }
};

/**
 * @brief Binary Indexed Tree
 */
#line 3 "DataStructure/2dbit.hpp"

template <class T> struct BIT2D {
    int n;
    vector<BIT<T>> d;
    vector<int> xs;
    vector<vector<int>> ys;
    vector<pair<ll, ll>> p;
    BIT2D() {}
    void push(ll x, ll y) {
        p.push_back({x, y});
    }
    void init() {
        rep(i, 0, p.size()) xs.push_back(p[i].first);
        sort(ALL(xs));
        xs.erase(unique(ALL(xs)), xs.end());
        n = xs.size() + 1;
        ys.resize(n);
        rep(j, 0, p.size()) {
            int s = upper_bound(ALL(xs), p[j].first) - xs.begin();
            for (int i = s; i < n; i += (i & -i))
                ys[i].push_back(p[j].second);
        }
        d.resize(n);
        rep(i, 0, n) {
            sort(ALL(ys[i]));
            ys[i].erase(unique(ALL(ys[i])), ys[i].end());
            d[i] = BIT<T>(ys[i].size() + 2);
        }
    }
    void add(ll x, ll y, T z = 1) {
        int s = upper_bound(ALL(xs), x) - xs.begin();
        for (int i = s; i < n; i += (i & -i)) {
            int idx = upper_bound(ALL(ys[i]), y) - ys[i].begin();
            d[i].add(idx, z);
        }
    }
    T sum(ll x, ll y) {
        T res = T();
        int s = upper_bound(ALL(xs), x) - xs.begin();
        for (int i = s; i; i -= (i & -i)) {
            int idx = upper_bound(ALL(ys[i]), y) - ys[i].begin();
            res += d[i].sum(idx + 1);
        }
        return res;
    }
    T sum(ll x1, ll y1, ll x2, ll y2) {
        return sum(x2, y2) - sum(x1 - 1, y2) - sum(x2, y1 - 1) +
               sum(x1 - 1, y1 - 1);
    }
};

/**
 * @brief 2D Binary Indexed Tree
 */

Back to top page