Loading [Contrib]/a11y/accessibility-menu.js
$\newcommand{\O}{\mathrm{O}}$ My Algorithm : kopricky アルゴリズムライブラリ

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

RangeUpdateQuery RangeAddQuery and RangeSumQuery

コードについての説明

区間更新 $a_i \leftarrow val (i \in [l, r))$, 区間加算 $a_i \leftarrow a_i + val (i \in [l, r))$, 区間和 $\underset{l \le i < r}{\mathrm{sum}} a_i$ のクエリを効率的に処理できる.
更新と加算の両方の遅延伝播をいい感じに処理すればできる.

時間計算量: 構築 $\O (n)$, 各クエリ $\O (\log n)$

コード

  1. template<typename T> class segtree {
  2. private:
  3.     int n,sz,h; vector<T> node, lazy_update, lazy_add; vector<bool> lazyFlag;
  4. public:
  5.     segtree(const vector<T> v) : n(1), sz((int)v.size()), h(0){
  6.         while(n < sz) n *= 2, h++;
  7.         node.resize(2*n, 0);
  8.         lazy_update.resize(2*n, 0); lazyFlag.resize(2*n, false);
  9.         lazy_add.resize(2*n, 0);
  10.         for(int i = 0; i < sz; i++) node[i+n] = v[i];
  11.         for(int i=n-1; i>=1; i--) node[i] = node[2*i] + node[2*i+1];
  12.     }
  13.     void eval(int k) {
  14.         if(lazyFlag[k]){
  15.             lazy_update[k] += lazy_add[k];
  16.             node[k] = lazy_update[k];
  17.             if(k < n) {
  18.                 lazy_add[2*k] = lazy_add[2*k+1] = 0;
  19.                 lazy_update[2*k] = lazy_update[2*k+1] = lazy_update[k] / 2;
  20.                 lazyFlag[2*k] = lazyFlag[2*k+1] = true;
  21.             }
  22.             lazy_add[k] = 0, lazyFlag[k] = false;
  23.         }else if(lazy_add[k] != 0){
  24.             node[k] += lazy_add[k];
  25.             if(k < n){
  26.                 lazy_add[2*k] += lazy_add[k] / 2; lazy_add[2*k+1] += lazy_add[k] / 2;
  27.             }
  28.             lazy_add[k] = 0;
  29.         }
  30.     }
  31.     void update(int a, int b, T x, int k=1, int l=0, int r=-1) {
  32.         if(r < 0) r = n;
  33.         eval(k);
  34.         if(b <= l || r <= a) return;
  35.         if(a <= l && r <= b){
  36.             lazy_update[k] = x*(r-l); lazyFlag[k] = true; eval(k);
  37.         }else{
  38.             update(a, b, x, 2*k, l, (l+r)/2); update(a, b, x, 2*k+1, (l+r)/2, r);
  39.             node[k] = node[2*k] + node[2*k+1];
  40.         }
  41.     }
  42.     void add(int a, int b, T x, int k=1, int l=0, int r=-1){
  43.         if(r < 0) r = n;
  44.         eval(k);
  45.         if(b <= l || r <= a) return;
  46.         if(a <= l && r <= b){
  47.             lazy_add[k] += x*(r-l); eval(k);
  48.         }else{
  49.             add(a, b, x, 2*k, l, (l+r)/2); add(a, b, x, 2*k+1, (l+r)/2, r);
  50.             node[k] = node[2*k] + node[2*k+1];
  51.         }
  52.     }
  53.     T query(int a, int b) {
  54.         a += n, b += n - 1;
  55.         for(int i = h; i > 0; i--) eval(a >> i), eval(b >> i);
  56.         b++;
  57.         T res1 = 0, res2 = 0;
  58.         while(a < b) {
  59.             if(a & 1) eval(a), res1 += node[a++];
  60.             if(b & 1) eval(--b), res2 += node[b];
  61.             a >>= 1, b >>= 1;
  62.         }
  63.         return res1 + res2;
  64.     }
  65.     void print(){for(int i = 0; i < sz; i++)cout<<query(i,i+1)<< " ";cout<<endl;}
  66. };

verify 用の問題

Atcoder : Deforestation 提出コード