Processing math: 100%
My Algorithm : kopricky アルゴリズムライブラリ

kopricky アルゴリズムライブラリ

BIT 1D RangeAddQuery and RangeSumQuery

コードについての説明

BIT を 2 つ持つことで, 区間加算, 区間和 のクエリを O(logn) で処理するデータ構造を実現できる. 実測がどっちが速いかはテストケースによる(こちらは区間加算の定数倍が少し重い).
1 つの BIT で区間加算, ある 1 点の値を求める というクエリを処理するやつ(imos 的にやるとできる)の応用版. 区間に線形関数を足すことができればよくてそれは 1 次の係数と定数項それぞれについて BIT を持てば実現可能.

時間計算量: 構築 O(n), クエリ O(logn)

コード

  1. template<typename T> class BIT {
  2. private:
  3. 	int n;
  4. 	vector<T> bit;
  5. public:
  6. 	void add(int i, const T x){
  7. 		i++;
  8. 		while(i < n){
  9. 			bit[i] += x, i += i & -i;
  10. 		}
  11. 	}
  12. 	T sum(int i) const {
  13. 		i++;
  14. 		T s = 0;
  15. 		while(i > 0){
  16. 			s += bit[i], i -= i & -i;
  17. 		}
  18. 		return s;
  19. 	}
  20. 	BIT(const int sz) : n(sz + 1), bit(n, 0){}
  21. };
  22.  
  23. template<typename T> class BIT_1D_RangeAdd_RangeSum {
  24. private:
  25. 	int n;
  26. 	BIT<T> bitc, biti;
  27. public:
  28. 	// 初期値はすべて 0
  29. 	BIT_1D_RangeAdd_RangeSum(const int sz) : n(sz), bitc(sz), biti(sz){}
  30. 	// [l, r) に val を加算
  31. 	void add(const int l, const int r, const T val){
  32. 		bitc.add(l, val), bitc.add(r, -val);
  33. 		biti.add(l, -val * (l - 1)), biti.add(r, val * (r - 1));
  34. 	}
  35. 	// [0, x] の和
  36. 	T sum(const int x) const {
  37. 		return bitc.sum(x) * x + biti.sum(x);
  38. 	}
  39. 	// [l, r) の和
  40. 	T sum(const int l, const int r) const {
  41. 		return sum(r-1) - sum(l-1);
  42. 	}
  43. 	void print(){
  44. 		for(int i = 0; i < n; i++){
  45. 			cout << sum(i, i+1) << " ";
  46. 		}
  47. 		cout << "\n";
  48. 	}
  49. };

verify 用の問題

AOJ : RSQ and RAQ 提出コード