動的Binary Indexed Tree
(data-structure/dynamic-binary-indexed-tree.hpp)

• View this file on GitHub
• Last update: 2021-08-10 23:14:36+09:00
• Include: #include "data-structure/dynamic-binary-indexed-tree.hpp"

動的Binary Indexed Tree

概要

Binary Indexed Treeを動的にしたライブラリ。

Binary Indexed Tree(BIT)は区間和と一点加算が配列長を$n$として時間計算量$\mathrm{O}(\log n)$で出来るが、空間計算量が$\mathrm{O}(n)$になるため$n$がメモリサイズより大きいときに使用できない。そこで、配列の代わりに連想配列を利用することで空間計算量を(クエリ数を$q$として)$\mathrm{O}(q \log n)$で抑えたものが動的Binary Indexed Treeである。

使い方

• DynamicBinaryIndexedTree<T>(int n): $[0, n]$を添え字の値として取れるBITを作成する。
• add(k, x): k番目の要素にxを加算する。
• operator[](k): k番目の要素を取得する。
• sum(k): 区間[0, k)の和を取得する。
• sum(l, r): 区間[l, r)の和を取得する。
• operator[](k): k番目の要素の値を取得する。
• lower_bound(w): 要素が全て非負の時、[0, k]の区間和がw以上となるような最小のkを求める。

Depends on

• Hash Map(可変長版) (data-structure/hash-map-variable-length.hpp)

Required by

• 動的二次元Binary Indexed Tree (data-structure-2d/dynamic-binary-indexed-tree-2d.hpp)

Verified with

• verify/verify-yosupo-ds/yosupo-point-add-rectangle-sum-bit2d.test.cpp

Code

#pragma once

#include "hash-map-variable-length.hpp"

template <typename S, typename T>
struct DynamicFenwickTree {
  S N;
  HashMap<S, T> data;
  explicit DynamicFenwickTree() = default;
  explicit DynamicFenwickTree(S size) { N = size + 1; }

  void add(S k, T x) {
    for (++k; k < N; k += k & -k) data[k] += x;
  }

  // [0, k)
  T sum(S k) const {
    if (k < 0) return 0;
    T ret = T();
    for (; k > 0; k -= k & -k) {
      const T* p = data.find(k);
      ret += p ? *p : T();
    }
    return ret;
  }

  // [a, b)
  T sum(S a, S b) const { return sum(b) - sum(a); }

  T operator[](S k) const { return sum(k + 1) - sum(k); }

  S lower_bound(T w) {
    if (w <= 0) return 0;
    S x = 0;
    for (S k = 1 << __lg(N); k; k >>= 1) {
      if (x + k <= N - 1 && data[x + k] < w) {
        w -= data[x + k];
        x += k;
      }
    }
    return x;
  }
};

/**
 * @brief 動的Binary Indexed Tree
 * @docs docs/data-structure/dynamic-binary-indexed-tree.md
 */

#line 2 "data-structure/dynamic-binary-indexed-tree.hpp"

#line 2 "data-structure/hash-map-variable-length.hpp"

template <typename Key, typename Val>
struct HashMap {
  using u32 = uint32_t;
  using u64 = uint64_t;

  u32 cap, s;
  vector<Key> keys;
  vector<Val> vals;
  vector<bool> flag;
  u64 r;
  u32 shift;
  Val DefaultValue;

  static u64 rng() {
    u64 m = chrono::duration_cast<chrono::nanoseconds>(
                chrono::high_resolution_clock::now().time_since_epoch())
                .count();
    m ^= m >> 16;
    m ^= m << 32;
    return m;
  }

  void reallocate() {
    cap <<= 1;
    vector<Key> k(cap);
    vector<Val> v(cap);
    vector<bool> f(cap);
    u32 sh = shift - 1;
    for (int i = 0; i < (int)flag.size(); i++) {
      if (flag[i]) {
        u32 hash = (u64(keys[i]) * r) >> sh;
        while (f[hash]) hash = (hash + 1) & (cap - 1);
        k[hash] = keys[i];
        v[hash] = vals[i];
        f[hash] = 1;
      }
    }
    keys.swap(k);
    vals.swap(v);
    flag.swap(f);
    --shift;
  }

  explicit HashMap()
      : cap(8),
        s(0),
        keys(cap),
        vals(cap),
        flag(cap),
        r(rng()),
        shift(64 - __lg(cap)),
        DefaultValue(Val()) {}

  Val& operator[](const Key& i) {
    u32 hash = (u64(i) * r) >> shift;
    while (true) {
      if (!flag[hash]) {
        if (s + s / 4 >= cap) {
          reallocate();
          return (*this)[i];
        }
        keys[hash] = i;
        flag[hash] = 1;
        ++s;
        return vals[hash] = DefaultValue;
      }
      if (keys[hash] == i) return vals[hash];
      hash = (hash + 1) & (cap - 1);
    }
  }

  // exist -> return pointer of Val
  // not exist -> return nullptr
  const Val* find(const Key& i) const {
    u32 hash = (u64(i) * r) >> shift;
    while (true) {
      if (!flag[hash]) return nullptr;
      if (keys[hash] == i) return &(vals[hash]);
      hash = (hash + 1) & (cap - 1);
    }
  }

  // return vector< pair<const Key&, val& > >
  vector<pair<Key, Val>> enumerate() const {
    vector<pair<Key, Val>> ret;
    for (u32 i = 0; i < cap; ++i)
      if (flag[i]) ret.emplace_back(keys[i], vals[i]);
    return ret;
  }

  int size() const { return s; }

  // set default_value
  void set_default(const Val& val) { DefaultValue = val; }
};

/**
 * @brief Hash Map(可変長版)
 * @docs docs/data-structure/hash-map.md
 */
#line 4 "data-structure/dynamic-binary-indexed-tree.hpp"

template <typename S, typename T>
struct DynamicFenwickTree {
  S N;
  HashMap<S, T> data;
  explicit DynamicFenwickTree() = default;
  explicit DynamicFenwickTree(S size) { N = size + 1; }

  void add(S k, T x) {
    for (++k; k < N; k += k & -k) data[k] += x;
  }

  // [0, k)
  T sum(S k) const {
    if (k < 0) return 0;
    T ret = T();
    for (; k > 0; k -= k & -k) {
      const T* p = data.find(k);
      ret += p ? *p : T();
    }
    return ret;
  }

  // [a, b)
  T sum(S a, S b) const { return sum(b) - sum(a); }

  T operator[](S k) const { return sum(k + 1) - sum(k); }

  S lower_bound(T w) {
    if (w <= 0) return 0;
    S x = 0;
    for (S k = 1 << __lg(N); k; k >>= 1) {
      if (x + k <= N - 1 && data[x + k] < w) {
        w -= data[x + k];
        x += k;
      }
    }
    return x;
  }
};

/**
 * @brief 動的Binary Indexed Tree
 * @docs docs/data-structure/dynamic-binary-indexed-tree.md
 */

Back to top page