Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <tuple>
- #include <random>
- using std::pair;
- using std::cin;
- using std::cout;
- using std::vector;
- using int64 = int64_t;
- using std::max;
- using std::min;
- class SegmentTree {
- public:
- int64 log_size;
- vector<int64> nodes = std::vector<int64>((2 << log_size) - 1);
- vector<int> SubtreeAdd;
- static int64 IntLog(int64 n) {
- int64 temp = 1;
- int64 ans = 0;
- while (temp < n) {
- temp *= 2;
- ++ans;
- }
- return ans;
- }
- static int64 Pow2(int64 n) {
- return 1 << n;
- }
- explicit SegmentTree(const vector<int64> &vec) : log_size(IntLog(vec.size())) {
- std::copy(vec.begin(), vec.end(), nodes.begin() + (1 << log_size) - 1);
- SubtreeAdd.assign(vec.size(), 0);
- for (int64 i = Pow2(log_size) - 2; i >= 0; --i) {
- nodes[i] = nodes[2 * i + 1] + nodes[2 * i + 2];
- }
- }
- void Modify(int64 l, int64 r, int64 val) {
- Modify(l, r, 0, 0, Pow2(log_size) - 1, val);
- }
- int64 GetSum(int64 l, int64 r) {
- return GetSum(l, r, 0, 0, Pow2(log_size) - 1);
- }
- private:
- int64 GetSum(int64 l, int64 r, int64 n, int64 nl, int64 nr) {
- if (l > r) {
- return 0;
- }
- if (l == nl && r == nr) {
- return nodes[n];
- }
- int64 mid = (nl + nr) / 2;
- return GetSum(l, min(r, mid), n * 2 + 1, nl, mid) +
- GetSum(max(l, mid + 1), r, n * 2 + 2, mid + 1, nr);
- }
- void push(int64 v, int64 vl, int64 vr) {
- if (SubtreeAdd[v]) {
- nodes[v] += SubtreeAdd[v] * (vr - vl + 1);
- if (vl != vr) {
- SubtreeAdd[2 * v + 1] += SubtreeAdd[v];
- SubtreeAdd[2 * v + 2] += SubtreeAdd[v];
- }
- SubtreeAdd[v] = 0;
- }
- }
- void Modify(int64 l, int64 r, int64 n, int64 nl, int64 nr, int64 val) {
- push(n, nl, nr);
- if (l > nr || r < nl) {
- return;
- }
- if (l <= nl && r >= nr) {
- nodes[n] += val;
- push(n, nl, nr);
- return;
- } else {
- int64 mid = (nl + nr) / 2;
- Modify(l, mid, n * 2 + 1, nl, mid, val);
- Modify(mid+1, r, n * 2 + 2, mid + 1, nr, val);
- nodes[n] = nodes[2 * n + 1] + nodes[2 * n + 2];
- }
- }
- };
- int main() {
- int64 n;
- cin >> n;
- vector<int64> vec(n);
- for (size_t i = 0; i < n; ++i) {
- cin >> vec[i];
- }
- SegmentTree st(vec);
- int k;
- cin >> k;
- for (size_t i = 0; i < k; ++i) {
- int num;
- cin >> num;
- if (num == 1) {
- int64 l, r;
- cin >> l >> r;
- cout << st.GetSum(l, r) << '\n';
- } else {
- int64 l, r, x;
- cin >> l >> r >> x;
- st.Modify(l, r, x);
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement