fork(1) download 
  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.             int pow = 1;
  101.             while (pow < n) { pow *= 2; }
  102.             data.assign(2 * pow, Node());
  103.         }
  104.  
  105.         /*******************************************************************************
  106.          *  Lazy propagation from node to its children
  107.          ******************************************************************************/
  108.         void push(int v, int l, int r, int m) {
  109.             if (data[v].extra != Traits::extraNeutral()) {
  110.                 Traits::push(
  111.                     NodeWrapper<Node&>(l, m, data[2*v+1]), 
  112.                     NodeWrapper<const Node&>(l, r, data[v])
  113.                 );
  114.                 Traits::push(
  115.                     NodeWrapper<Node&>(m+1, r, data[2*v+2]), 
  116.                     NodeWrapper<const Node&>(  l, r, data[v])
  117.                 );
  118.                 data[v].extra = Traits::extraNeutral();
  119.             }
  120.         }
  121.  
  122.         /*******************************************************************************
  123.          *  Update node using children values
  124.          ******************************************************************************/
  125.         void pull(int v, int l, int r, int m) {
  126.             assert(data[v].extra == Traits::extraNeutral());
  127.             Traits::pull(
  128.                 NodeWrapper<Node&>(  l, r, data[v]), 
  129.                 NodeWrapper<const Node&>(  l, m, data[2*v+1]), 
  130.                 NodeWrapper<const Node&>(m+1, r, data[2*v+2])
  131.             );
  132.         }
  133.  
  134.         /*******************************************************************************
  135.          *  Build segtree from array with given values
  136.          ******************************************************************************/
  137.         template<typename T>
  138.         void build(const std::vector<T>& arr, const int v, const int tl, const int tr) {
  139.             if (tl == tr) {
  140.                 data[v] = Node(arr[tl]);
  141.             } else {
  142.                 const int tm = (tl + tr) / 2;
  143.                 build(arr, 2*v+1,   tl, tm);
  144.                 build(arr, 2*v+2, tm+1, tr);
  145.                 pull(v, tl, tr, tm);
  146.             }
  147.         }
  148.  
  149.         template<typename T>
  150.         void build(const std::vector<T>& arr) { 
  151.             resize((int)arr.size());
  152.             build(arr, 0, 0, n-1);
  153.         }
  154.  
  155.         /*******************************************************************************
  156.          *  Get-query on range [ql, qr]
  157.          ******************************************************************************/
  158.         Node get(int ql, int qr, const int v, const int tl, const int tr) {
  159.             if (ql == tl && qr == tr) {
  160.                 return data[v];
  161.             } else {
  162.                 int tm = (tl + tr) / 2;
  163.                 push(v, tl, tr, tm);
  164.                 Node ret;
  165.                 if (qr <= tm) {
  166.                     ret = get(ql, qr, 2*v+1,   tl, tm);
  167.                 } else if (ql > tm) {
  168.                     ret = get(ql, qr, 2*v+2, tm+1, tr);
  169.                 } else {
  170.                     const auto lt = get(  ql, tm, 2*v+1,   tl, tm);
  171.                     const auto rt = get(tm+1, qr, 2*v+2, tm+1, tr);
  172.                     Traits::pull(
  173.                         NodeWrapper<Node&>(  ql, qr, ret), 
  174.                         NodeWrapper<const Node&>(  ql, tm, lt), 
  175.                         NodeWrapper<const Node&>(tm+1, qr, rt)
  176.                     );
  177.                 }
  178.                 pull(v, tl, tr, tm);
  179.                 return ret;
  180.             }
  181.         }
  182.  
  183.         Value get(const int ql, const int qr) { return get(ql, qr, 0, 0, n-1).getValue(ql, qr); }
  184.  
  185.         /*******************************************************************************
  186.          *  Update query on range [ql, qr] by extra
  187.          ******************************************************************************/
  188.         void update(const int ql, const int qr, const Extra& extra, const int v, const int tl, const int tr) {
  189.             if (ql == tl && tr == qr) {
  190.                 Traits::push(
  191.                     NodeWrapper<Node&>(tl, tr, data[v]),
  192.                     NodeWrapper<Node>(ql, qr, Node(Traits::valueNeutral(), extra))
  193.                 );
  194.             } else {
  195.                 int tm = (tl + tr) / 2;
  196.                 push(v, tl, tr, tm);
  197.                 if (qr <= tm) {
  198.                     update(ql, qr, extra, 2*v+1, tl, tm);
  199.                 } else if (ql > tm) {
  200.                     update(ql, qr, extra, 2*v+2,tm+1,tr);
  201.                 } else {
  202.                     update(ql, tm, extra, 2*v+1,   tl, tm);
  203.                     update(tm+1, qr, extra, 2*v+2, tm+1, tr);
  204.                 }
  205.                 pull(v, tl, tr, tm);
  206.             }
  207.         }
  208.  
  209.         void update(const int ql, const int qr, const Extra& extra) {
  210.             update(ql, qr, extra, 0, 0, n-1); 
  211.         }
  212.  
  213.     };
  214.  
  215.     /*******************************************************************************
  216.      *  Traits for maximal value on segment. 
  217.      *  Get-query:    get maximal value in segment [l, r]
  218.      *  Update-query: add const to each value in segment [l, r]
  219.      ******************************************************************************/
  220.     template<typename Value, typename Extra>
  221.     struct TraitsMaxAdd {
  222.         // Definition of neutral element for `Value`:
  223.         static Value valueNeutral() { return std::numeric_limits<Value>::min(); }
  224.         // Definition of neutral element for `Extra`:
  225.         static Extra extraNeutral() { return Extra(0); }
  226.         // Definition of how should combine `Extra` with `Value`:
  227.         template<typename Node>
  228.         static Value getValue(const Node& src) {
  229.             return src.value() + src.extra();
  230.         }
  231.         // Definition of how should combine `Value` with `Value` (children to root):
  232.         template<typename NodeRoot, typename NodeLt, typename NodeRt>
  233.         static void pull(NodeRoot root, const NodeLt& lt, const NodeRt& rt) {
  234.             root.value() = std::max(getValue(lt), getValue(rt));
  235.         }
  236.         // Definition of how should combine `Extra` with `Extra`:
  237.         template<typename NodeDst, typename NodeSrc>
  238.         static void push(NodeDst dst, const NodeSrc& src) {
  239.             dst.extra() += src.extra();
  240.         }
  241.     };   
  242. }
  243.  
  244. int main() {
  245.     // Creating queries 1) arr[l..r] += x and 2) max(arr[l..r])
  246.     const int n = (int)1e6;
  247.     const int q = (int)1e6;
  248.     std::mt19937 gen;
  249.     std::uniform_int_distribution<int> dist(0,n-1);
  250.     std::vector<int> arr(n);
  251.     for (auto &it : arr) { it = dist(gen); }
  252.     std::vector<int> queryType(q), queryLeft(q), queryRight(q), queryExtra(q);
  253.     for (int i = 0; i < q; ++i) {
  254.         queryType[i] = 1 + dist(gen) % 2;
  255.         queryLeft[i] = dist(gen);
  256.         queryRight[i] = dist(gen);
  257.         if (queryLeft[i] > queryRight[i]) { std::swap(queryLeft[i], queryRight[i]); }
  258.         queryExtra[i] = dist(gen) - n / 2;
  259.     }
  260.     // Create SegmentTree
  261.     SegmentTreeLazy::SegmentTree<int64_t, int64_t, SegmentTreeLazy::TraitsMaxAdd<int64_t,int64_t>> segtree;
  262.     segtree.build(arr);
  263.     int64_t checkValue = 0;
  264.     for (int i = 0; i < q; ++i) {
  265.         if (queryType[i] == 1) {
  266.             segtree.update(queryLeft[i], queryRight[i], queryExtra[i]);
  267.         } else {
  268.             checkValue += segtree.get(queryLeft[i], queryRight[i]);
  269.         }
  270.     }
  271.     std::cout << "checkValue = " << checkValue << std::endl;
  272.     return 0;
  273. }
Success #stdin #stdout 0.7s 15248KB
comments (?)
stdin 
Standard input is empty
stdout 
checkValue = 128540600627068
https://ideone.com/74Vpj7
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!