Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- typedef long long int64;
- const int MAXN = 500001;
- struct __Segment_tree
- {
- public:
- static const int64 INF = 9223372036854775807;
- __Segment_tree()
- {
- data = new int64[MAXN << 2 | 1];
- lazy_tag = new int64[MAXN << 2 | 1];
- if(data == nullptr)
- ERROR("__Segment_tree.data[] cannot get the memory!");
- if(lazy_tag == nullptr)
- ERROR("__Segment_tree.lazy_tag[] cannot get the memory!");
- }
- ~__Segment_tree()
- {
- if(data != nullptr) delete []data;
- if(lazy_tag != nullptr)delete []lazy_tag;
- data = nullptr;
- lazy_tag = nullptr;
- }
- int N;
- int arr[MAXN];
- inline void Build_sum()
- {
- find_sum_ = true;
- find_max_ = find_min_ = false;
- build_sum(1, 1, N);
- }
- inline void Build_max()
- {
- find_max_ = true;
- find_sum_ = find_min_ = false;
- build_max(1, 1, N);
- }
- inline void Build_min()
- {
- find_min_ = true;
- find_max_ = find_sum_ = false;
- build_min(1, 1, N);
- }
- inline void Update(int l, int r, int64 value)
- {
- update(1, N, 1, l, r ,value);
- }
- inline int64 Query_sum(int l, int r)
- {
- if(find_sum_)
- return query_sum(1, N, 1, l, r);
- ERROR("USING WRONG FUNCTION: Query_sum");
- }
- inline int64 Query_min(int l, int r)
- {
- if(find_min_)
- return query_min(1, N, 1, l, r);
- ERROR("USING WRONG FUNCTION: Query_min");
- }
- inline int64 Query_max(int l, int r)
- {
- if(find_max_)
- return query_max(1, N, 1, l, r);
- ERROR("USING WRONG FUNCTION: Query_max");
- }
- private:
- int64 *data, *lazy_tag;
- bool find_max_,find_min_,find_sum_;
- void ERROR(char s[])
- {
- puts("");
- puts("######ERROR######");
- puts(s);
- puts("####END ERROR####");
- puts("");
- }
- void build_sum(int now, int left, int right)
- {
- if(left == right) data[now] = arr[left];
- else
- {
- int mid = (left + right) >> 1;
- build_sum(now << 1, left, mid);
- build_sum(now << 1 | 1, mid + 1, right);
- data[now] = data[now << 1] + data[now << 1 | 1];
- }
- }
- void build_max(int now, int left, int right)
- {
- if(left == right) data[now] = arr[left];
- else
- {
- int mid = (left + right) >> 1;
- build_max(now << 1, left, mid);
- build_max(now << 1 | 1, mid + 1, right);
- data[now] = max(data[now << 1], data[now << 1 | 1]);
- }
- }
- void build_min(int now, int left, int right)
- {
- if(left == right) data[now] = arr[left];
- else
- {
- int mid = (left + right) >> 1;
- build_min(now << 1, left, mid);
- build_min(now << 1 | 1, mid + 1, right);
- data[now] = min(data[now << 1], data[now << 1 | 1]);
- }
- }
- void push_down(int left, int right, int now)
- {
- int mid = (left + right) >> 1;
- data[now << 1] += lazy_tag[now] * (mid - left + 1);
- data[now << 1 | 1] += lazy_tag[now] * (right - mid);
- lazy_tag[now << 1] += lazy_tag[now];
- lazy_tag[now << 1 | 1] += lazy_tag[now];
- lazy_tag[now] = 0;
- }
- void update(int left, int right, int now, int l, int r, int64 value)
- {
- if(l <= left && right <= r)
- {
- lazy_tag[now] += value;
- data[now] += value * (right - left + 1);
- }
- else
- {
- int mid = (left + right) >> 1;
- if(lazy_tag[now]) push_down(left, right, now);
- if(l <= mid) update(left, mid, now << 1, l, r, value);
- if(mid < r) update(mid + 1, right, now << 1 | 1, l, r, value);
- data[now] = data[now << 1] + data[now << 1 | 1];
- }
- }
- int64 query_sum(int left, int right, int now, int l, int r)
- {
- int mid = (left + right) >> 1;
- if(l <= left && right <= r) return data[now];
- if(r < left || right < l) return 0;
- if(lazy_tag[now]) push_down(left, right, now);
- return query_sum(left, mid, now << 1, l, r) + query_sum(mid + 1, right, now << 1 | 1, l, r);
- }
- int64 query_max(int left, int right, int now, int l,int r)
- {
- int mid = (left + right) >> 1;
- if(l <= left && right <= r) return data[now];
- if(r < left || right < l) return -INF;
- if(lazy_tag[now]) push_down(left, right, now);
- return max(query_max(left, mid, now << 1, l, r), query_max(mid + 1, right, now << 1 | 1, l, r));
- }
- int64 query_min(int left, int right, int now, int l,int r)
- {
- int mid = (left + right) >> 1;
- if(l <= left && right <= r) return data[now];
- if(r < left || right < l) return INF;
- if(lazy_tag[now]) push_down(left, right, now);
- return min(query_min(left, mid, now << 1, l, r), query_min(mid + 1, right, now << 1 | 1, l, r));
- }
- };
- /**
- __Segment_tree segment_T;
- segment_T.N = N; //set the length of array
- for(...) set segment_T.arr[i]; //set the origin data
- //Build the Segment tree
- #you can build lots times
- 1. segment_T.Build_sum();
- 2. segment_T.Build_max();
- 3. segment_T.Build_min();
- //Query
- 1. segment_T.Query_sum(lower, upper);
- 2. segment_T.Query_min(lower, upper);
- 3. segment_T.Query_max(lower, upper);
- segment_T.Update(lower, upper, addition); //Update
- */
Add Comment
Please, Sign In to add comment