分块（区间修改，单点查询

 1 #include<bits/stdc++.h>
 2 
 3 using namespace std;
 4 typedef long long ll;
 5 const int maxn = 1e5 + 10;
 6 const int inf = 0x3f3f3f3f;
 7 int dir[10][10] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
 8 int pos[maxn], add[maxn], a[maxn], r[maxn], l[maxn], n;
 9 
10 inline int read()
11 {
12     char ch = getchar(); int k = 0, f = 1;
13     while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
14     while(ch >= '0' && ch <= '9') {k = k * 10 + ch - '0'; ch = getchar();}
15     return k * f;
16 }
17 
18 inline void change(int L, int R, int d)
19 {
20     int p = pos[L], q = pos[R];
21     if(p == q) for(int i = L; i <= R; ++i) a[i] += d;//如果在一组里，直接暴力修改
22     else
23     {
24         for(int i = p + 1; i <= q - 1; ++i) add[i] += d;//将i的后一组和j的前一组之间的所有组加d
25         for(int i = L; i <= r[p]; ++i) a[i] += d;//暴力修改l到l右边界各值
26         for(int i = l[q]; i <= R; ++i) a[i] += d;//暴力修改r左边界到r各值
27     }
28 }
29 int main()
30 {
31     std::ios::sync_with_stdio(false);std::cin.tie(0);
32     n = read();
33     for(int i = 1; i <= n; ++i)
34     {
35         a[i] = read();
36     }
37     int t = sqrt(n);//总共t块
38     for(int i = 1; i <= t; ++i)
39     {
40         l[i] = (i - 1) * t + 1;
41         r[i] = i * t;
42     }//定每块左边界，右边界。
43 
44     if(r[t] < n) t++, l[t] = r[t - 1] + 1, r[t] = n;//为多出那块赋左右边界值，再让块总数加1.
45     for(int i = 1; i <= t; ++i)
46     {
47         for(int j = l[i]; j <= r[i]; ++j)
48         {
49             pos[j] = i;
50         }
51     }//每个数字定块，j数属于i块。
52 
53     for(int i = 1; i <= n; ++i)
54     {
55         int opt, L, R, C;
56         opt = read(), L = read(), R = read(), C = read();
57         if(!opt) change(L, R, C);
58         else
59         {
60             int q = pos[R];
61             cout<<a[R] + add[q]<<'
';//查询q的值
62         }
63     }
64     return 0;
65 }
分块 （区间修改，单点查询

分块（区间修改，单点查询
