树状数组的基本操作

一、单点修改，区间查询

题目描述：

给出一个长度为n的序列，有m个操作，分别为询问[l,r]的区间和，和将x位置上的值增加C。

思路：

可以使用线性数组进行操作，对于每一次询问，修改的时间复杂度为O(1)，询问的时间复杂度为O(n)。如果数量n较大，这种操作必定会超时，所以我们尝试用前缀和来维护这个数组。使用前缀和的方法，明显可以看出来，在每一次询问中，查询的时间复杂度为O(1)，修改的时间复杂度为O(n)。所以这种方法也不太靠谱，那么在这种情况下我们就可以使用树状数组了。

提到树状数组我们就不得不提到三个函数：lowbit函数、修改函数和求区间和的函数，以下我们一个个介绍。

lowbit函数：

 int lowbit(int x){
        return x&(-x);
    }

lowbit函数计算的是 一个数化为二进制从右往左看第一个为1位置代表的数，例如5的二级制101，那么lobit(5)=1。lowbit函数在树状数组里面用处很大。对于一个子节点a，a+lowbit(a)就是他的父节点，这样操作就可直接降低操作次数，从而达到降低时间复杂度的效果。

现在我们来理解一下这行代码:

我们知道,对于一个数的负数就等于对这个数取反+1

以二进制数11010为例:11010的补码为00101,加1后为00110,两者相与便是最低位的1

其实很好理解,补码和原码必然相反,所以原码有0的部位补码全是1,补码再+1之后由于进位那么最末尾的1和原码，最右边的1一定是同一个位置(当遇到第一个1的时候补码此位为0,由于前面会进一位,所以此位会变为1)。

所以我们只需要进行a&(-a)就可以取出最低位的1了
会了lowbit,我们就可以进行区间查询和单点更新了!!!

修改函数:

void add(int x,int c){//在下标为x的数组里加上c
        while(x<=n){ //n为序列的个数
        sum[x]+=c;
        x+=lowbit(x);
        }
}

修改函数很好理解，就是在每一个x位置及其父节点上加上需要加上的c就行了，主要是要理解为什么x会+=lowbit(x)。

查询函数：

int query(int x){
    int ans=0;
    while(x>0){
         ans+=sum[x];
         x-=lowbit(x);
    }
}

三个函数都理解了，我们来看个板子题。很简单，直接照猫画虎就行了。
https://loj.ac/problem/130​​​​

#include <iostream>
#include <cstring>
using namespace std;
const long long maxn = 1e6;
long long n, m, i, v, c[maxn + 10];
long long sum(long long x) {
    long long ans = 0;
    while (x > 0) {
        ans += c[x];
        x -= x & (-x);
    }
    return ans;
}
void update(long long x, long long v) {
    while (x <= n) {
        c[x] += v;
        x += x & (-x);
    }
}
int main() {
    cin >> n >> m;
    memset(c, 0, sizeof(c));
    for (i = 1; i <= n; i++) {
        cin >> v;
        update(i, v);
    }
    while (m--) {
        long long x, y, z;
        cin >> x >> y >> z;
        if (x == 1) {
            update(y, z);
        } else if (x == 2) {
            long long res = 0;
            res = sum(z) - sum(y - 1);
            cout << res << endl;
        }
    }
    return 0;
}

二、区间修改，单点查询

主要思想：差分。
设原数组为, 设原数组 $a\left[i\right]$a[i]，差分数组为 $d\left[i\right]$d[i]，则 $d\left[i\right]=a\left[i\right]-a[i-1](i\>=1)$d[i]=a[i]−a[i−1](i>=1)，则 $a\left[i\right]={\sum }_{j=1}^{i}d\left[j\right]$a[i]=∑j=1i​d[j]，可以通过求的前缀和查询。
当给区间 $[l,r]$[l,r]加上 $x$x的时候， $a\left[l\right]$a[l]与前一个元素 $a[l-1]$a[l−1]的差增加了 $x$x， $a[r+1]$a[r+1]与 $a\left[r\right]$a[r]的差减少了 $x$x。根据数组 $d\left[i\right]$d[i]的定义，只需给 $a\left[l\right]$a[l]加上 $x$x, 给 $a[r+1]$a[r+1]减去 $x$x即可。

long long lowbit(ll x){
	return x&(-x);
}
void add(long long x,long long c){
		while(x<=n){
			sum[x]+=c;
			x+=lowbit(x);
		}
}
long long update_add(l,r,x){//修改的区间[l,r],修改的数值x
	add(l,x);
	add(r+1,-x);
}

传送门：https://loj.ac/problem/131

题目描述：
这是一道模板题。
给定数列 $a\left[1\right],a\left[2\right],\dots ,a\left[n\right],$a[1],a[2],…,a[n],你需要一次进行 $q$q个操作，操作有两类：
$\bullet$∙ $1$1 $l$l $r$r $x$x $:$: 对于所有 $i$i $\in$∈ $[l,r]$[l,r],将 $a\left[i\right]$a[i]加上 $x$x；
$\bullet$∙ $2$2 $i:$i: 给定 $i,求a\left[i\right]的值。$i,求a[i]的值。
保证 $1\le l\le r\le n，\mid x\mid \le 10^6。$1≤l≤r≤n，∣x∣≤106。
输出格式：
对于每个 $2$2 $i$i操作，输出一行，每行有一个整数，表示所求的结果。
样例
样例输入
3 2
1 2 3
1 1 3 0
2 2
样例输出
2
数据范围与提示：
对于所有数据， $1\le n,q\le 10^6,\mid a\left[i\right]\mid \le 10^6,1\le l\le r\le n,\mid x\mid \le 10^6。$1≤n,q≤106,∣a[i]∣≤106,1≤l≤r≤n,∣x∣≤106。

#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
const ll maxn = 1e6;
ll a[maxn + 5], n, m, sum[maxn + 5], i;
ll lowbit(ll x) { return x & (-x); }
void add(ll x, ll c) {
    while (x <= n) {
        sum[x] += c;
        x += lowbit(x);
    }
}
ll find(ll x) {
    ll ans = 0;
    while (x > 0) {
        ans += sum[x];
        x -= lowbit(x);
    }
    return ans;
}
int main() {
    memset(a, 0, sizeof(a));
    memset(sum, 0, sizeof(sum));
    scanf("%lld%lld", &n, &m);
    for (i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
        add(i, a[i] - a[i - 1]);
    }
    while (m--) {
        ll x;
        scanf("%lld", &x);
        if (x == 1) {
            ll l, r, y;
            scanf("%lld%lld%lld", &l, &r, &y);
            add(l, y);
            add(r + 1, -y);
        } else if (x == 2) {
            ll y;
            scanf("%lld", &y);
            printf("%lld\n", find(y));
        }
    }
}

三、区间修改，单点查询

主要思想：差分思想。
我们基于上一个问题的“差分”思路，考虑一下如何在构建的树状数组中求前缀和。由差分数组的定义我们可以得出 $：a\left[x\right]={\sum }_{i=1}^{x}d\left[i\right]$：a[x]=∑i=1x​d[i]，那么可以得出：
${\sum }_{i=1}^{p}a\left[i\right]={\sum }_{i=1}^p{\sum }_{j=1}^{i}d\left[j\right]$∑i=1p​a[i]=∑i=1p​∑j=1i​d[j]
上述式子还可以简化，我们可以看出 $d\left[1\right]用了p次,d\left[2\right]用了p-1次\dots \dots 依次类推d\left[i\right]用了p-i+1次，所以讲上述式子简化为：$d[1]用了p次,d[2]用了p−1次……依次类推d[i]用了p−i+1次，所以讲上述式子简化为：
${\sum }_{i=1}^p{\sum }_{j=1}^{i}d\left[j\right]={\sum }_{i=1}^{p}d\left[i\right]\ast (p-i+1)=(p+1)\ast {\sum }_{i=1}^{p}d\left[i\right]-{\sum }_{i=1}^{p}d\left[i\right]\ast i$∑i=1p​∑j=1i​d[j]=∑i=1p​d[i]∗(p−i+1)=(p+1)∗∑i=1p​d[i]−∑i=1p​d[i]∗i
那么我们可以维护两个数组的前缀和：
$sum1\left[i\right]=d\left[i\right]$sum1[i]=d[i]
$sum2\left[i\right]=d\left[i\right]\ast i$sum2[i]=d[i]∗i

long long lowbit(long long x){
 	return x&(-x);
} 
void add(long long x,long long y){
 	long long tx=x;
 	while(x<=n){
	    sum1[x]+=y;
	    sum2[x]+=tx*y;
  	    x+=lowbit(x);
        }
}
long long find(long long x){
	long long res=0;
 	long long tx=x;
 	while(x){
  	  res+=(tx+1)*sum1[x]-sum2[x];
  	  x-=lowbit(x);
 	}
 	return res;
}

搞懂了之后我们来看个模板题。
传送门：https://loj.ac/problem/132

$题目描述：$题目描述：
$这是一道模板题。$这是一道模板题。
$给定数列a\left[1\right],a\left[2\right],\dots ,a\left[n\right]，你需要依次进行q个操作，操作有两类：$给定数列a[1],a[2],…,a[n]，你需要依次进行q个操作，操作有两类：
$\bullet$∙ $1$1 $l$l $r$r $x$x $：给定$：给定 $l$l $r$r $x$x， $对于所有$对于所有 $i\in [l,r]$i∈[l,r]， $将$将 $a\left[i\right]$a[i] $加上$加上 $x\left(换言之，将a\right[l],a[l+1],\dots ,a[r\left]分别加上x\right);$x(换言之，将a[l],a[l+1],…,a[r]分别加上x);
$\bullet$∙ $l$l $r$r $:$: 给定 $l$l $r$r ， $求{\sum }_{i=l}^{r}a\left[i\right]的值（换言之，求a\left[l\right]+a[l+1]+\cdots +a\left[r\right]的值)。$求∑i=lr​a[i]的值（换言之，求a[l]+a[l+1]+⋯+a[r]的值)。
$输入格式$输入格式
$第一行包含2个正整数n,q,表示数列长度和询问个数。保证1\le n,q\le 10^6。$第一行包含2个正整数n,q,表示数列长度和询问个数。保证1≤n,q≤106。
$第二行n个整数a\left[1\right],a\left[2\right],\dots ,a\left[n\right]，表示初始数列。保证\mid a\left[i\right]\mid \le 10^6。$第二行n个整数a[1],a[2],…,a[n]，表示初始数列。保证∣a[i]∣≤106。
$接下来q行，每行一个操作，为以下两种之一：$接下来q行，每行一个操作，为以下两种之一： $1$1 $l$l $r$r $x$x $：对于所有i\in [l,r]，将a\left[i\right]加上x；2lr：输出{\sum }_{i=l}^{r}a\left[i\right]的值。保证1\le l\le r\le n,\mid x\mid \le 10^6。$：对于所有i∈[l,r]，将a[i]加上x；2lr：输出∑i=lr​a[i]的值。保证1≤l≤r≤n,∣x∣≤106。
$输出格式对于每个2lr操作，输出一行，每行有一个整数，表示所求的结果。$输出格式对于每个2lr操作，输出一行，每行有一个整数，表示所求的结果。
$样例样例$样例样例
$输入$输入
5 10
2 6 6 1 1
2 1 4
1 2 5 10
2 1 3
2 2 3
1 2 2 8
1 2 3 7
1 4 4 10
2 1 2
1 4 5 6
2 3 4
$样例输出$样例输出
15
34
32
33
50
$数据范围与提示对于所有数据，1\le n,q\le 10^6,\mid a\left[i\right]\mid \le 10^6,1\le l\le r\le n,\mid x\mid \le 10^6。$数据范围与提示对于所有数据，1≤n,q≤106,∣a[i]∣≤106,1≤l≤r≤n,∣x∣≤106。

#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
ll n,m,i;
const ll maxn=1e6+5;
ll c1[maxn],c2[maxn];
ll a[maxn];
int lowbit(ll x){
    return x&(-x);
}
void add(ll p, ll x){
	ll y=p;
    for(;p<=n;p+=p&(-p))
        c1[p]+=x,c2[p] += x * y;
 
}
ll find(ll x){
    ll ans=0,y;
    y=x;
    for(;x;x-=x&(-x)){
        ans+=(y+1)*c1[x]-c2[x];
    }
    return ans;
} 
int main(){		
	scanf("%lld%lld",&n,&m);
 	memset(a,0,sizeof(a));
    	for(i=1;i<=n;i++)    scanf("%lld",&a[i]);
    	for(i=1;i<=n;i++){
        add(i,a[i]-a[i-1]);
    } 	
    	while(m--){
    	ll x;
    	scanf("%lld",&x);
    	if(x==1){
    		ll l,r,c;
    		scanf("%lld%lld%lld",&l,&r,&c);
    		add(l,c);
    		add(r+1,-c);
		}
    	else if(x==2){
    		ll l,r;
    		scanf("%lld%lld",&l,&r);
    		printf("%lld\n",find(r)-find(l-1));
		}
	}
    return 0; 
}

第一次写博客，如果哪里写错了，欢迎指出。