Emiliatan

__Segment_tree

Jan 25th, 2019
106
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.61 KB | None | 0 0
  1. typedef long long int64;
  2.  
  3. const int MAXN = 500001;
  4.  
  5. struct __Segment_tree
  6. {
  7.     public:
  8.     static const int64 INF = 9223372036854775807;
  9.     __Segment_tree()
  10.     {
  11.         data = new int64[MAXN << 2 | 1];
  12.         lazy_tag = new int64[MAXN << 2 | 1];
  13.         if(data == nullptr)
  14.             ERROR("__Segment_tree.data[] cannot get the memory!");
  15.         if(lazy_tag == nullptr)
  16.             ERROR("__Segment_tree.lazy_tag[] cannot get the memory!");
  17.     }
  18.     ~__Segment_tree()
  19.     {
  20.         if(data != nullptr) delete []data;
  21.         if(lazy_tag != nullptr)delete []lazy_tag;
  22.         data = nullptr;
  23.         lazy_tag = nullptr;
  24.     }
  25.     int N;
  26.     int arr[MAXN];
  27.     inline void Build_sum()
  28.     {
  29.         find_sum_ = true;
  30.         find_max_ = find_min_ = false;
  31.         build_sum(1, 1, N);
  32.     }
  33.     inline void Build_max()
  34.     {
  35.         find_max_ = true;
  36.         find_sum_ = find_min_ = false;
  37.         build_max(1, 1, N);
  38.     }
  39.     inline void Build_min()
  40.     {
  41.         find_min_ = true;
  42.         find_max_ = find_sum_ = false;
  43.         build_min(1, 1, N);
  44.     }
  45.     inline void Update(int l, int r, int64 value)
  46.     {
  47.         update(1, N, 1, l, r ,value);
  48.     }
  49.     inline int64 Query_sum(int l, int r)
  50.     {
  51.         if(find_sum_)
  52.             return query_sum(1, N, 1, l, r);
  53.         ERROR("USING WRONG FUNCTION: Query_sum");
  54.     }
  55.     inline int64 Query_min(int l, int r)
  56.     {
  57.         if(find_min_)
  58.             return query_min(1, N, 1, l, r);
  59.         ERROR("USING WRONG FUNCTION: Query_min");
  60.     }
  61.     inline int64 Query_max(int l, int r)
  62.     {
  63.         if(find_max_)
  64.             return query_max(1, N, 1, l, r);
  65.         ERROR("USING WRONG FUNCTION: Query_max");
  66.     }
  67.  
  68.  
  69.     private:
  70.     int64 *data, *lazy_tag;
  71.     bool find_max_,find_min_,find_sum_;
  72.     void ERROR(char s[])
  73.     {
  74.         puts("");
  75.         puts("######ERROR######");
  76.         puts(s);
  77.         puts("####END ERROR####");
  78.         puts("");
  79.     }
  80.  
  81.     void build_sum(int now, int left, int right)
  82.     {
  83.         if(left == right) data[now] = arr[left];
  84.         else
  85.         {
  86.             int mid = (left + right) >> 1;
  87.             build_sum(now << 1, left, mid);
  88.             build_sum(now << 1 | 1, mid + 1, right);
  89.             data[now] = data[now << 1] + data[now << 1 | 1];
  90.         }
  91.     }
  92.     void build_max(int now, int left, int right)
  93.     {
  94.         if(left == right) data[now] = arr[left];
  95.         else
  96.         {
  97.             int mid = (left + right) >> 1;
  98.             build_max(now << 1, left, mid);
  99.             build_max(now << 1 | 1, mid + 1, right);
  100.             data[now] = max(data[now << 1], data[now << 1 | 1]);
  101.         }
  102.     }
  103.     void build_min(int now, int left, int right)
  104.     {
  105.         if(left == right) data[now] = arr[left];
  106.         else
  107.         {
  108.             int mid = (left + right) >> 1;
  109.             build_min(now << 1, left, mid);
  110.             build_min(now << 1 | 1, mid + 1, right);
  111.             data[now] = min(data[now << 1], data[now << 1 | 1]);
  112.         }
  113.     }
  114.     void push_down(int left, int right, int now)
  115.     {
  116.         int mid = (left + right) >> 1;
  117.         data[now << 1] += lazy_tag[now] * (mid - left + 1);
  118.         data[now << 1 | 1] += lazy_tag[now] * (right - mid);
  119.         lazy_tag[now << 1] += lazy_tag[now];
  120.         lazy_tag[now << 1 | 1] += lazy_tag[now];
  121.         lazy_tag[now] = 0;
  122.     }
  123.     void update(int left, int right, int now, int l, int r, int64 value)
  124.     {
  125.         if(l <= left && right <= r)
  126.         {
  127.             lazy_tag[now] += value;
  128.             data[now] += value * (right - left + 1);
  129.         }
  130.         else
  131.         {
  132.             int mid = (left + right) >> 1;
  133.             if(lazy_tag[now]) push_down(left, right, now);
  134.             if(l <= mid) update(left, mid, now << 1, l, r, value);
  135.             if(mid < r) update(mid + 1, right, now << 1 | 1, l, r, value);
  136.             data[now] = data[now << 1] + data[now << 1 | 1];
  137.         }
  138.     }
  139.     int64 query_sum(int left, int right, int now, int l, int r)
  140.     {
  141.         int mid = (left + right) >> 1;
  142.         if(l <= left && right <= r) return data[now];
  143.         if(r < left || right < l) return 0;
  144.         if(lazy_tag[now]) push_down(left, right, now);
  145.         return query_sum(left, mid, now << 1, l, r) + query_sum(mid + 1, right, now << 1 | 1, l, r);
  146.     }
  147.     int64 query_max(int left, int right, int now, int l,int r)
  148.     {
  149.         int mid = (left + right) >> 1;
  150.         if(l <= left && right <= r) return data[now];
  151.         if(r < left || right < l) return -INF;
  152.         if(lazy_tag[now]) push_down(left, right, now);
  153.         return max(query_max(left, mid, now << 1, l, r), query_max(mid + 1, right, now << 1 | 1, l, r));
  154.     }
  155.     int64 query_min(int left, int right, int now, int l,int r)
  156.     {
  157.         int mid = (left + right) >> 1;
  158.         if(l <= left && right <= r) return data[now];
  159.         if(r < left || right < l) return INF;
  160.         if(lazy_tag[now]) push_down(left, right, now);
  161.         return min(query_min(left, mid, now << 1, l, r), query_min(mid + 1, right, now << 1 | 1, l, r));
  162.     }
  163. };
  164.  
  165. /**
  166. __Segment_tree segment_T;
  167.  
  168. segment_T.N = N;                             //set the length of array
  169.  
  170. for(...) set segment_T.arr[i];               //set the origin data
  171.  
  172.  
  173.                                              //Build the Segment tree
  174. #you can build lots times
  175. 1. segment_T.Build_sum();
  176. 2. segment_T.Build_max();
  177. 3. segment_T.Build_min();
  178.                                              //Query
  179. 1. segment_T.Query_sum(lower, upper);
  180. 2. segment_T.Query_min(lower, upper);
  181. 3. segment_T.Query_max(lower, upper);
  182.  
  183. segment_T.Update(lower, upper, addition);    //Update
  184.  
  185. */
Add Comment
Please, Sign In to add comment