BIT-区间修改单点查询

　　正好刷题时碰到了这个之前遇到过的问题，类似的还有区间修改区间查询，以后学了会补上。

　　我们知道BIT只支持单点修改区间查询，如果现在问题变成每次让一个区间的数同时变化，然后询问的是某一个点得值的时候该怎么办。

线段树当然可以，但是很麻烦，不仅是写的麻烦，复杂度也相对较高，下面介绍一下BIT的做法。

　　可以把原数组a转化为一个差分数组b，让b[i]=a[i]-a[i-1] ,这样的话a[i]=b[1]+b[2]+...+b[i] ,例如 a[]={1,3,9,4} 则b[]={1,2,6,-5} ,不难发现

b的前缀和就是a中的数，对b数组建立树状数组，查询的时候显然就是利用sum函数进行。区间修改的时候，对于[l,r] ,我们只要add(l,d)

和add(r+1,-d)就好了，相当于把这个问题又转化为了区间查询单点修改。

　　例题: https://loj.ac/problem/6277

给出一个长为

第一行输入一个数字

第二行输入 $aia_iai，以空格隔开。$

接下来输入

若

若 $ara_rar 的值（lll 和 ccc 忽略）。$

对于每次询问，输出一行一个数字表示答案。

样例输入

样例输出

2
5

对于 $100\%100% 的数$

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int N,C[50050];
 4 int lowbit(int x){return x&-x;}
 5 void add(int x,int d){
 6     while(x<=N){
 7         C[x]+=d;
 8         x+=lowbit(x);
 9     }
10 }
11 int sum(int x){
12     int ans=0;
13     while(x){
14         ans+=C[x];
15         x-=lowbit(x);
16     }
17     return ans;
18 }
19 int main(){
20     int n,i,j;
21     int opt,l,r,c,a,b;
22     while(cin>>n){b=0,N=n;
23         for(i=1;i<=n;++i) scanf("%d",&a),add(i,a-b),b=a;
24         for(i=1;i<=n;++i){
25             scanf("%d%d%d%d",&opt,&l,&r,&c);
26             //l++,r++;
27             if(opt){
28                 printf("%d
",sum(r));
29             }
30             else{
31                 add(l,c);
32                 add(r+1,-c);
33             }
34         }
35         memset(C,0,sizeof(C));
36     }
37     return 0;
38 }

BIT-区间修改单点查询

题目描述

输入格式

输出格式

样例

样例输入

样例输出

数据范围与提示