【模板】线段树1（洛谷P3372）

  1 #include <iostream>
  2 #include <cstdio>
  3 
  4 using namespace std;
  5 
  6 template <class T>
  7 inline void read(T &s)
  8 {
  9     s = 0;
 10     int w = 1;
 11     char ch = getchar();
 12     while (ch < '0' || ch > '9')
 13     {
 14         if (ch == '-')
 15             w = -1;
 16         ch = getchar();
 17     }
 18     while (ch >= '0' && ch <= '9')
 19     {
 20         s = s * 10 + (ch ^ '0');
 21         ch = getchar();
 22     }
 23     s *= w;
 24 }
 25 
 26 template <class T>
 27 inline void write(T x)
 28 {
 29     if (x < 0)
 30     {
 31         putchar('-');
 32         x = -x;
 33     }
 34     if (x > 9)
 35         write(x / 10);
 36     putchar(x % 10 + '0');
 37 }
 38 #define int long long
 39 const int N = 1e5 + 7;
 40 int n, m, a[N], ans[N << 2], tag[N << 2];
 41 inline int ls(int x) { return x << 1; }     // 返回左儿子下标 2*i
 42 inline int rs(int x) { return x << 1 | 1; } // 返回右儿子下标 2*i+1
 43 inline void push_up(int pos)                // 计算当前结点的值
 44 {
 45     ans[pos] = ans[ls(pos)] + ans[rs(pos)];
 46 }
 47 void build(int p, int l, int r)
 48 {
 49     tag[p] = 0;
 50     if (l == r) // 到达叶节点
 51     {
 52         ans[p] = a[l];
 53         return;
 54     }
 55     int mid = l + r >> 1;
 56     build(ls(p), l, mid);     // 建立左子树
 57     build(rs(p), mid + 1, r); // 建立右子树
 58     push_up(p);               // 更新当前结点的值
 59 }
 60 inline void f(int p, int l, int r, int k) // 区间修改 + 打lazy标记
 61 {
 62     tag[p] = tag[p] + k;
 63     ans[p] = ans[p] + k * (r - l + 1);
 64 }
 65 inline void push_down(int p, int l, int r) // 将当前结点的lazy标记下传
 66 {
 67     int mid = l + r >> 1;
 68     f(ls(p), l, mid, tag[p]);
 69     f(rs(p), mid + 1, r, tag[p]);
 70     tag[p] = 0;
 71 }
 72 inline void update(int nl, int nr, int l, int r, int p, int k) // 更新区间
 73 {
 74     if (nl <= l && r <= nr) // [nl,l,r,nr] 当前区间被完全覆盖
 75     {
 76         ans[p] += k * (r - l + 1);
 77         tag[p] += k;
 78         return;
 79     }
 80     push_down(p, l, r);
 81     int mid = l + r >> 1;
 82     if (nl <= mid) // 若与左儿子有交集
 83         update(nl, nr, l, mid, ls(p), k);
 84     if (nr > mid)
 85         update(nl, nr, mid + 1, r, rs(p), k);
 86     push_up(p);
 87 }
 88 int query(int q_x, int q_y, int l, int r, int p) // 返回区间和
 89 {
 90     int res = 0;
 91     if (q_x <= l && r <= q_y)
 92         return ans[p];
 93     int mid = l + r >> 1;
 94     push_down(p, l, r);
 95     if (q_x <= mid)
 96         res += query(q_x, q_y, l, mid, ls(p));
 97     if (q_y > mid)
 98         res += query(q_x, q_y, mid + 1, r, rs(p));
 99     return res;
100 }
101 
102 signed main()
103 {
104     // 输入
105     read(n), read(m);
106     for (int i = 1; i <= n; ++i)
107         read(a[i]);
108     build(1, 1, n);
109     while (m--)
110     {
111         int opt, x, y, k;
112         read(opt), read(x), read(y);
113         switch (opt)
114         {
115         case 1:
116             read(k);
117             update(x, y, 1, n, 1, k);
118             break;
119         case 2:
120             printf("%lld\n", query(x, y, 1, n, 1));
121             break;
122         }
123     }
124     // system("pause");
125     return 0;
126 }