【题目链接】

洛谷 P3374 【模板】树状数组 1

【题目考点】

一. 树状数组

树状数组是在线算法，可以维护区间和，区间最值。其实现单点修改、区间修改、区间查询时间复杂度都为$O(\log n)$

1. lowbit函数

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

本题中x为自然数
假设x>0：
记x的补码为：0D...(x位)...D10...(y位)...0
最高位为0，而后有x位，每位的值可能不同，最后一位1后面有y位0，y可能为0。
-x的原码为：1D...(x位)...D10...(y位)...0
-x的反码为：1R...(x位)...R01...(y位)...1 (R表示D取反后的值。如果D为0，则R为1。如果D为1，则R为0）
-x的补码为：1R...(x位)...R10...(y位)...0
求 x & -x

    0D...(x位)...D10...(y位)...0 
 &  1R...(x位)...R10...(y位)...0
 ----------------------------------- 
    0...(x+1位)..010...(y位)...0

得到的结果是x最低位1与后面的y位0合在一起构成的数值，也就是最低位1的位权。
当x为0时，x & -x为0，返回0，依然符合“最低位1的位权”的概念。

因此lowbit(x)求的是x在二进制下最低位1的位权，为x在二进制下最低位的1和后面的0组成的数的数值。

例：十进制数$12$在二进制下为$(1100{)}_2$，那么lowbit(12)为$(100{)}_2$，即十进制下的4。

2. 树状数组的定义

设原序列为$a_1,a_2,...,a_n$，$a_i$表示序列的第i个数，共有n个数。
树状数组为$t$，$t_i=\sum _{j=i-lowbit(i)+1}^x{a}_j$，即$t_i$为$a$序列区间$[i-lowbit(i)+1,i]$的区间和，或者说以$a_i$为结尾的长为$lowbit(i)$的区间的区间和。

树状数组满足如下性质：

1. 每个内部结点$t_i$保存以它为根的子树中所有叶子结点的和。
2. 每个内部结点$t_i$的子结点个数等于lowbit(i)的位数。
3. 每个内部结点$t_i$的父结点是$t_{i+lowbit(i)}$。
4. 树状数组下标不能从0开始，必须从1开始。
5. 树的深度为$O(logn)$。

【题目考点】

解法1：树状数组

使用树状数组维护区间和，进行单点修改和区间查询

1. 单点修改

设update函数完成对元素$a_i$的修改，假设$a_i$的值增加$v$（v可以是负数），那么在树状数组表示的树中，所有$a_i$的祖先结点都表示包含$a_i$的一段区间的区间和，因此这些祖先结点的值都要增加$v$。
设循环控制变量x初值为i。每次循环将x增加lowbit(x)，使x变为其父结点，直到x大于n时结束循环。循环体内，树状数组x位置的值$t_x$增加$v$。

2. 区间查询

记$a$序列区间$[1,i]$中元素加和为$s_i$。
设sum函数，调用sum(i)可以求出$s_i$
$a$序列区间$[1,i]$中元素加和为$a$序列$[1,i-lowbit(i)]$中元素的加和再加上$[i-lowbit(i)+1,i]$中元素的加和，即$t_i$。
因此$s_i=s_{i-lowbit(i)}+t_i$
不断使用该递推式，可以将$s_i$分成多个$t$中的元素相加。
设求和变量s初值为0。循环控制变量x初值为i，每次循环x减少lowbit(x)。循环体内让s增加$t_x$。最后s的值即为$s_i$

求a序列区间$[l,r]$中元素的加和，即可用a序列前r项的和减去前l-1项的和求出，即$s_r-s_{l-1}$

使用树状数组维护区间和，每次单点修改的时间复杂度为$O(\log n)$，区间查询的复杂度为$O(\log n)$。

【题解代码】

#include <bits/stdc++.h>
using namespace std; 
#define N 500005
int n, tree[N];//原数组为a，a[i]是输入的第i个数 tree：树状数组 维护区间和 
int lowbit(int x)
{
	return x & -x;
}
void update(int i, int v)//a[i] += v 单点修改 
{
	for(int x = i; x <= n; x += lowbit(x))
		tree[x] += v; 
}
int sum(int i)//a[1]+...+a[i] 区间查询 
{
	int s = 0;
	for(int x = i; x > 0; x -= lowbit(x))
		s += tree[x];
	return s;
} 
int query(int l, int r)//求[l, r]的区间和 
{
	return sum(r)-sum(l-1);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int m, x, y, k, v, op;
	cin >> n >> m;
	for(int i = 1; i <= n; ++i)
	{
		cin >> v;
		update(i, v);
	}
	while(m--)
	{
		cin >> op;
		if(op == 1)
		{
			cin >> x >> k;
			update(x, k);
		}
		else
		{
			cin >> x >> y;
			cout << query(x, y) << '\n';
		}
	}
	return 0;
}