截流法进行区间更新

截流法进行区间更新，这种算法在某些特定情况下很简便，但是其局限性也很明显，针对各类型的题目酌情使用，之所以将其挑出来单独写一篇是因为其思想没见过，很是新颖，所以在这里值得一提。

算法性能：在进行区间修改和单点修改时的算法时间复杂度时都是 O(1),但是进行查询时的时间复杂度是 O(n),对于这种情况，所以一般在进行查询次数较少的情况下，选择这种方法才可取。
参考题目：牛客--区间 (interval)

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 using namespace std;
 5 
 6 const int MaxN=1e6+10;
 7 int arr[MaxN];
 8 
 9 void show(int n)
10 {
11     for(int i=1;i<=n;++i)
12     {
13         printf("%d ",arr[i]);
14     }
15     printf("
");
16 }
17 
18 int main()
19 {
20     int n,m;
21     int l,r,p;
22     long long ans=0;
23     scanf("%d%d",&n,&m);//数组内元素个数,及操作个数
24 
25     for(int i=1;i<=n;++i)    scanf("%d",&arr[i]);
26 
27     for(int i=n;i>=2;--i)  //预处理
28     {
29         arr[i]=arr[i]-arr[i-1];
30     }
31     show(n);
32 
33     while(m--)
34     {
35         scanf("%d%d%d",&l,&r,&p);
36         arr[l]+=p;
37         arr[r+1]-=p;
38         show(n);
39     }
40 
41     for(int i=1;i<=n;++i)
42     {
43         arr[i]+=arr[i-1];
44     }
45     scanf("%d%d",&l,&r);
46 
47     show(n);
48 
49     for(int i=l;i<=r;++i)
50     {
51         ans+=arr[i];
52     }
53     printf("%lld
",ans);
54 
55 
56     return 0;
57 }

/*
in:
10 1
1 2 3 4 5 6 7 8 9 10
2 6 4
1 10

out:
10 1
1 2 3 4 5 6 7 8 9 10
1 1 1 1 1 1 1 1 1 1
2 6 4
1 5 1 1 1 1 -3 1 1 1
1 10
1 6 7 8 9 10 7 8 9 10
75
*/