fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. namespace SegmentTreeLazy {
  4.  
  5.     /*******************************************************************************
  6.      *  SegmentTree<Value, Extra, Traits> - segment tree class with lazy propagation, 0-indexed
  7.      *  Default operations: minimal value on segment and addition on segment for int64_t type
  8.      *  Use Traits<Value,Extra> for definition of:
  9.      *      1)  neutral element for `Value`;
  10.      *      2)  neutral element for `Extra`;
  11.      *      3)  how should combine `Extra` with `Value`;
  12.      *      4)  how should combine `Value` with `Value` (children to root);
  13.      *      5)  how should combine `Extra` with `Extra`;
  14.      *  See examples below: TraitsMinAdd<Value, Extra>
  15.      ******************************************************************************/
  16.  
  17.     /*******************************************************************************
  18.      *  Traits for minimal value on segment. 
  19.      *  Get-query:    get minimal value in segment [l, r]
  20.      *  Update-query: add const to each value in segment [l, r]
  21.      ******************************************************************************/
  22.     template<typename Value, typename Extra>
  23.     struct TraitsMinAdd {
  24.         // Definition of neutral element for `Value`:
  25.         static Value valueNeutral() { return std::numeric_limits<Value>::max(); }
  26.         // Definition of neutral element for `Extra`:
  27.         static Extra extraNeutral() { return Extra(0); }
  28.         // Definition of how should combine `Extra` with `Value`:
  29.         template<typename Node>
  30.         static Value getValue(const Node& src) {
  31.             return src.value() + src.extra();
  32.         }
  33.         // Definition of how should combine `Value` with `Value` (children to root):
  34.         template<typename NodeRoot, typename NodeLt, typename NodeRt>
  35.         static void pull(NodeRoot root, const NodeLt& lt, const NodeRt& rt) {
  36.             root.value() = std::min(getValue(lt), getValue(rt));
  37.         }
  38.         // Definition of how should combine `Extra` with `Extra`:
  39.         template<typename NodeDst, typename NodeSrc>
  40.         static void push(NodeDst dst, const NodeSrc& src) {
  41.             dst.extra() += src.extra();
  42.         }
  43.     };
  44.  
  45.     /*******************************************************************************
  46.      *  Additional traits, implemented below 
  47.      ******************************************************************************/
  48.     template<typename Value, typename Extra>  struct TraitsMaxAdd;
  49.  
  50.     /*******************************************************************************
  51.      *  SegmentTree, see description above
  52.      ******************************************************************************/
  53.     template<typename Value = int64_t, typename Extra = int64_t, typename Traits = TraitsMinAdd<Value, Extra> >
  54.     struct SegmentTree {
  55.  
  56.         /*******************************************************************************
  57.          *  Node class
  58.          ******************************************************************************/
  59.         struct Node {
  60.             Value value;
  61.  
  62.             Extra extra;
  63.  
  64.             Node(Value value_ = Traits::valueNeutral(), Extra extra_ = Traits::extraNeutral())
  65.                 : value(value_), extra(extra_) { }
  66.  
  67.             Value getValue(int l, int r) const { return Traits::getValue(NodeWrapper<Node>(l, r, *this)); }
  68.         };
  69.  
  70.         /*******************************************************************************
  71.          *  NodeWrapper class
  72.          ******************************************************************************/
  73.         template<typename NodeType>
  74.         struct NodeWrapper {
  75.             int l, r;
  76.             NodeType node;
  77.             NodeWrapper(int l_, int r_, NodeType node_)
  78.                 : l(l_), r(r_), node(node_) { }
  79.             int  left() const { return l; }
  80.             int right() const { return r; }
  81.             int   mid() const { return (l+r)/2; }
  82.             int   len() const { return r - l + 1; }
  83.             Value& value() { return node.value; }
  84.             Extra& extra() { return node.extra; }
  85.             const Value& value() const { return node.value; }
  86.             const Extra& extra() const { return node.extra; }
  87.         };
  88.  
  89.         /*******************************************************************************
  90.          *  SegmentTree public data: n - number of items, data - vector for nodes
  91.          ******************************************************************************/
  92.         int n; std::vector<Node> data;
  93.  
  94.  
  95.         /*******************************************************************************
  96.          *  Resize segment tree data to needed size
  97.          ******************************************************************************/
  98.         void resize(int n_) {
  99.             n = n_;
  100.             data.assign(2 * n, Node());
  101.         }
  102.  
  103.         /*******************************************************************************
  104.          *  Lazy propagation from node to its children
  105.          ******************************************************************************/
  106.         void push(int v, int l, int r, int m) {
  107.             if (data[v].extra != Traits::extraNeutral()) {
  108.                 Traits::push(
  109.                     NodeWrapper<Node&>(l, m, data[v+1]), 
  110.                     NodeWrapper<const Node&>(l, r, data[v])
  111.                 );
  112.                 Traits::push(
  113.                     NodeWrapper<Node&>(m+1, r, data[v+2*(m-l+1)]), 
  114.                     NodeWrapper<const Node&>(  l, r, data[v])
  115.                 );
  116.                 data[v].extra = Traits::extraNeutral();
  117.             }
  118.         }
  119.  
  120.         /*******************************************************************************
  121.          *  Update node using children values
  122.          ******************************************************************************/
  123.         void pull(int v, int l, int r, int m) {
  124.             assert(data[v].extra == Traits::extraNeutral());
  125.             Traits::pull(
  126.                 NodeWrapper<Node&>(  l, r, data[v]), 
  127.                 NodeWrapper<const Node&>(  l, m, data[v+1]), 
  128.                 NodeWrapper<const Node&>(m+1, r, data[v+2*(m-l+1)])
  129.             );
  130.         }
  131.  
  132.         /*******************************************************************************
  133.          *  Build segtree from array with given values
  134.          ******************************************************************************/
  135.         template<typename T>
  136.         void build(const std::vector<T>& arr, const int v, const int tl, const int tr) {
  137.             if (tl == tr) {
  138.                 data[v] = Node(arr[tl]);
  139.             } else {
  140.                 const int tm = (tl + tr) / 2;
  141.                 build(arr, v+1,   tl, tm);
  142.                 build(arr, v+2*(tm-tl+1), tm+1, tr);
  143.                 pull(v, tl, tr, tm);
  144.             }
  145.         }
  146.  
  147.         template<typename T>
  148.         void build(const std::vector<T>& arr) { 
  149.             resize((int)arr.size());
  150.             build(arr, 0, 0, n-1);
  151.         }
  152.  
  153.         /*******************************************************************************
  154.          *  Get-query on range [ql, qr]
  155.          ******************************************************************************/
  156.         Node get(int ql, int qr, const int v, const int tl, const int tr) {
  157.             if (ql == tl && qr == tr) {
  158.                 return data[v];
  159.             } else {
  160.                 int tm = (tl + tr) / 2;
  161.                 push(v, tl, tr, tm);
  162.                 Node ret;
  163.                 if (qr <= tm) {
  164.                     ret = get(ql, qr, v+1,   tl, tm);
  165.                 } else if (ql > tm) {
  166.                     ret = get(ql, qr, v+2*(tm-tl+1), tm+1, tr);
  167.                 } else {
  168.                     const auto lt = get(  ql, tm, v+1,   tl, tm);
  169.                     const auto rt = get(tm+1, qr, v+2*(tm-tl+1), tm+1, tr);
  170.                     Traits::pull(
  171.                         NodeWrapper<Node&>(  ql, qr, ret), 
  172.                         NodeWrapper<const Node&>(  ql, tm, lt), 
  173.                         NodeWrapper<const Node&>(tm+1, qr, rt)
  174.                     );
  175.                 }
  176.                 pull(v, tl, tr, tm);
  177.                 return ret;
  178.             }
  179.         }
  180.  
  181.         Value get(const int ql, const int qr) { return get(ql, qr, 0, 0, n-1).getValue(ql, qr); }
  182.  
  183.         /*******************************************************************************
  184.          *  Update query on range [ql, qr] by extra
  185.          ******************************************************************************/
  186.         void update(const int ql, const int qr, const Extra& extra, const int v, const int tl, const int tr) {
  187.             if (ql == tl && tr == qr) {
  188.                 Traits::push(
  189.                     NodeWrapper<Node&>(tl, tr, data[v]),
  190.                     NodeWrapper<Node>(ql, qr, Node(Traits::valueNeutral(), extra))
  191.                 );
  192.             } else {
  193.                 int tm = (tl + tr) / 2;
  194.                 push(v, tl, tr, tm);
  195.                 if (qr <= tm) {
  196.                     update(ql, qr, extra, v+1, tl, tm);
  197.                 } else if (ql > tm) {
  198.                     update(ql, qr, extra, v+2*(tm-tl+1),tm+1,tr);
  199.                 } else {
  200.                     update(ql, tm, extra, v+1,   tl, tm);
  201.                     update(tm+1, qr, extra, v+2*(tm-tl+1), tm+1, tr);
  202.                 }
  203.                 pull(v, tl, tr, tm);
  204.             }
  205.         }
  206.  
  207.         void update(const int ql, const int qr, const Extra& extra) {
  208.             update(ql, qr, extra, 0, 0, n-1); 
  209.         }
  210.  
  211.     };
  212.  
  213.     /*******************************************************************************
  214.      *  Traits for maximal value on segment. 
  215.      *  Get-query:    get maximal value in segment [l, r]
  216.      *  Update-query: add const to each value in segment [l, r]
  217.      ******************************************************************************/
  218.     template<typename Value, typename Extra>
  219.     struct TraitsMaxAdd {
  220.         // Definition of neutral element for `Value`:
  221.         static Value valueNeutral() { return std::numeric_limits<Value>::min(); }
  222.         // Definition of neutral element for `Extra`:
  223.         static Extra extraNeutral() { return Extra(0); }
  224.         // Definition of how should combine `Extra` with `Value`:
  225.         template<typename Node>
  226.         static Value getValue(const Node& src) {
  227.             return src.value() + src.extra();
  228.         }
  229.         // Definition of how should combine `Value` with `Value` (children to root):
  230.         template<typename NodeRoot, typename NodeLt, typename NodeRt>
  231.         static void pull(NodeRoot root, const NodeLt& lt, const NodeRt& rt) {
  232.             root.value() = std::max(getValue(lt), getValue(rt));
  233.         }
  234.         // Definition of how should combine `Extra` with `Extra`:
  235.         template<typename NodeDst, typename NodeSrc>
  236.         static void push(NodeDst dst, const NodeSrc& src) {
  237.             dst.extra() += src.extra();
  238.         }
  239.     };   
  240. }
  241.  
  242. int main() {
  243.     // Creating queries 1) arr[l..r] += x and 2) max(arr[l..r])
  244.     const int n = (int)1e6;
  245.     const int q = (int)1e6;
  246.     std::mt19937 gen;
  247.     std::uniform_int_distribution<int> dist(0,n-1);
  248.     std::vector<int> arr(n);
  249.     for (auto &it : arr) { it = dist(gen); }
  250.     std::vector<int> queryType(q), queryLeft(q), queryRight(q), queryExtra(q);
  251.     for (int i = 0; i < q; ++i) {
  252.         queryType[i] = 1 + dist(gen) % 2;
  253.         queryLeft[i] = dist(gen);
  254.         queryRight[i] = dist(gen);
  255.         if (queryLeft[i] > queryRight[i]) { std::swap(queryLeft[i], queryRight[i]); }
  256.         queryExtra[i] = dist(gen) - n / 2;
  257.     }
  258.     // Create SegmentTree
  259.     SegmentTreeLazy::SegmentTree<int64_t, int64_t, SegmentTreeLazy::TraitsMaxAdd<int64_t,int64_t>> segtree;
  260.     segtree.build(arr);
  261.     int64_t checkValue = 0;
  262.     for (int i = 0; i < q; ++i) {
  263.         if (queryType[i] == 1) {
  264.             segtree.update(queryLeft[i], queryRight[i], queryExtra[i]);
  265.         } else {
  266.             checkValue += segtree.get(queryLeft[i], queryRight[i]);
  267.         }
  268.     }
  269.     std::cout << "checkValue = " << checkValue << std::endl;
  270.     return 0;
  271. }
Success #stdin #stdout 0.77s 15248KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
checkValue = 128540600627068
https://ideone.com/i0CgjZ
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!