E - 树状数组 1[GDUT_22级寒假训练专题五]

E - 树状数组 1

题意

已知一个数列，你需要进行下面两种操作：

求出某区间每一个数的和

lowbit函数

定义一个函数\(f=lowbit(x\，这个函数的值是\(x\的二进制表达式中只保留最低位\(1\得到的十进制数

\[(6_{10}=(110_2 \]

那么\(lowbit(6\就等于\(2\，因为\((110_2\中最低位（就是从右往左数的第二位）对应的数是\((10_2=(2_{10}\

\[2^{k−1} \]

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

原理：
根据计算机补码的性质。
补码就是原码的反码加一
如：

\[(110_2=(6_{10} \]

\[(001_2 \]

加一：

\[(010_2 \]

会逢1一直进位直到遇到0，且这个0变成了1，所以这个数最后面构造了一个 100… 串。只有一个\(1\,因此进行&运算后除了该位上存在\(1\，其他位都是\(0\（反码的最低位\(0\变成\(1\，与反码取反前的原码相同都是\(1\）,进而得到二进制表达式中只保留最低位\(1\得到的十进制数

树状数组的定义

大小相同的数组

与前缀和不同的是，树状数组的一个位置 i 存储的是从 i 开始，（包括 i）向前\(t_i\个元素的和
\(t_i\就是最大的可以整除 \(i\ 的\(2\的幂（通过上述\(lowbit\函数可以得到）

树状数组的性质

设树状数组为b
性质1：有上述定义得到$b[k] = \sum_{k-lowbit(k+1}^{k} $
性质2：父节点 \(b[dad] = b[k] + lowbit(k\

树状数组单点修改

根据性质2可以改造出对树状数组单点修改的函数
\(add(int \ k,int \ x\功能：下标为k的增加x

void add(int k,int x{
	while(k <= n{	//不能超范围
		b[k] += x;
		k += lowbit(k;	//维护父节点
	}
}

注意：空数组本身就是一个树状数组(和均为0,因此原数组输入数据维护树状数组b时可以直接\(add(i,a_i\

树状数组区间查询

r的区间和:sum[1r] - sum[1~l-1]
根据性质1：

LL getsum(int l,int r{		
	l --;
	LL s1 = 0;
	while(l{
		s1 += b[l];
		l -= lowbit(l;
	}
	LL s2 = 0;
	while(r{
		s2 += b[r];
		r -= lowbit(r;
	}
	return s2 - s1;
}

最终代码

点击查看代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;

#define X first
#define Y second

typedef pair<int,int> pii;
typedef long long LL;
const char nl = '\n';
const int N = 1e6+10;
const int M = 2e5+10;
int n,m;
int a,b[N];

int lowbit(int x{
	return x & -x;
}
void add(int k,int x{
	while(k <= n{
		b[k] += x;
		k += lowbit(k;
	}
}
LL getsum(int l,int r{
	l --;
	LL s1 = 0;
	while(l{
		s1 += b[l];
		l -= lowbit(l;
	}
	LL s2 = 0;
	while(r{
		s2 += b[r];
		r -= lowbit(r;
	}
	return s2 - s1;
} 

void solve({
	cin >> n >> m;
	for(int i = 1; i <= n; i ++ {
		cin >> a;
		add(i,a;
	}
	while(m -- {
		int op;
		cin >> op;
		if(op == 1{
			int k,x;
			cin >> k >> x;
			add(k,x;
		}
		else{
			int l,r;
			cin >> l >> r;
			cout << getsum(l,r << nl;
		}
	}
}

int main({
	ios::sync_with_stdio(false;
	cin.tie(0,cout.tie(0;

	solve(;
}

编程笔记 » E - 树状数组 1[GDUT_22级寒假训练专题五]