引入
题目描述
给定\(n\)个数\(a[1],a[2],a[3]...a[n]\),现在又下面两种操作:
1.询问区间\([x,y]\)的和,并输出。
2.将下标为\(x\)的数增加\(val\)。
一共\(x\)此操作
\(1\le n,m\le 100000\),保证在\(int\)范围内。
方法一:暴力枚举
定义数组\(a\)储存\(n\)个元素。
求区间和的时间复杂度为O(n),将\(a[x]\)增加\(val\)的时间复杂度为O(1),总时间复杂度为O(nm)。
为什么超时?
因为每次求和的速度太慢了
前缀和
定义数组\(sum\),表示前缀和
求区间和的时间复杂度为O(1),将\(a[x]\)增加\(val\)的时间复杂度为O(n)。
因为每一次进行增加操作,就需要更新所有的前缀和,所以总的时间复杂度为O(mn)。
总结
所以,我们应该选取折中的方案
树形数组
基本思想
因为任意正整数都可以写成不重复的2的整数次幂的相加形式,所以对于区间\([1,x]\)可以分解为\(log(x)\)个小区间
分解的小区间的特点
若区间结尾为\(y\),则区间长度\(=y\)的二进制下最小的次幂
求解\(y\)的二进制下最小的次幂
可是我们应该怎么求解\(y\)的二进制下最小的次幂,这就需要引入一个新函数\(lowbit\)。
定义\(lowbit(x)\):
表示\(x\)(\(x\)为非负整数)的二进制下最小的\(2\)次幂。就是\(x\)的二进制下最低为的&1&以及后面的&0&构成的结构。
求解\(lowbit(x)\):
设\(x\)的第\(k\)为为\(1\),第\(0~k-1\)位都是\(0\)
先把\(x\)取反,此时第\(k\)位变为\(0\),第\(0~k-1\)都为\(1\)。
再令\(x=x+1\),此时因为进位,第\(k\)位变为\(0\),第\(0~k-1\)为都是\(0\)。同时,因为取反操作,第\(k+1\)位到最高位都与原来相反。
再进行与运算:n&(~n+1)
因为在计算机中数字以补码储存,所以~n+1=-n
代码
写法一:
int lowbit(x){
return x&(-x);
}
写法二:
int lowbit(int x){
return x&(~x+1);
}
基本算法
创建数组\(c\)保存存储数据的徐杰\(a\)的区间长的\(lowbit(x)\)的区间和,即区间\([x-lowbit(x)+1,x]\)中所有的数的和,数组\(c\)可以看一个树形结构。
模板
求解\(lowbit\)
解释:求出\(x\)的\(lowbit\)。
inline int lowbit(int x){
return x&(-x);
}
单点增加
为了维护数组\(c\),与\(x\)有关的每个点都要处理
解释:将位置位\(x\)的元素增加\(val\)。
inline void updata(int x,int val){
for(int i=x;i<=n;i+=lowbit(i))
c[i]+=val;
}
访问区间
解释:返回\([1,x]的总和\)
inline int sum(int x){
int ans=0;
for(int i=x;i>0;i-=lowbit(i))
ans+=c[i];
return ans;
}
例题
「HDU1166」敌兵布阵
题目背景
C国的死对头A国这段时间正在进行军事演习,所以C国间谍头子Derek和他手下Tidy又开始忙乎了。
A国在海岸线沿直线布置了N个工兵营地,Derek和Tidy的任务就是要监视这些工兵营地的活动情况。
由于采取了某种先进的监测手段,所以每个工兵营地的人数C国都掌握的一清二楚,每个工兵营地的人数都有可能发生变动,可能增加或减少若干人手,但这些都逃不过C国的监视。
中央情报局要研究敌人究竟演习什么战术,所以Tidy要随时向Derek汇报某一段连续的工兵营地一共有多少人,例如Derek问:“Tidy,马上汇报第3个营地到第10个营地共有多少人!”
Tidy就要马上开始计算这一段的总人数并汇报。但敌兵营地的人数经常变动,而Derek每次询问的段都不一样,所以Tidy不得不每次都一个一个营地的去数,很快就精疲力尽了。
Derek对Tidy的计算速度越来越不满:"你个死肥仔,算得这么慢,我炒你鱿鱼!”Tidy想:“你自己来算算看,这可真是一项累人的工作!我恨不得你炒我鱿鱼呢!”
无奈之下,Tidy只好打电话向计算机专家Windbreaker求救,Windbreaker说:“死肥宅,叫你平时做多点acm题和看多点算法书,现在尝到苦果了吧!”Tidy说:"我知错了。。。"
但Windbreaker已经挂掉电话了。Tidy很苦恼,这么算他真的会崩溃的,聪明的读者,你能写个程序帮他完成这项工作吗?不过如果你的程序效率不够高的话,Tidy还是会受到Derek的责骂的。
输入
第一行一个整数T,表示有T组数据。
每组数据第一行一个正整数N(N<=50000),表示敌人有N个工兵营地,接下来有N个正整数,第i个正整数ai代表第i个工兵营地里开始时有ai个人(1<=ai<=50)。
接下来每行有一条命令,命令有4种形式:
(1)Add i j,i和j为正整数,表示第i个营地增加j个人(j不超过30)
(2)Sub i j ,i和j为正整数,表示第i个营地减少j个人(j不超过30);
(3)Query i j ,i和j为正整数,i<=j,表示询问第i到第j个营地的总人数;
(4)End 表示结束,这条命令在每组数据最后出现;
每组数据最多有40000条命令
输出
对第i组数据,首先输出“Case i:”和回车,
对于每个Query询问,输出一个整数并回车,表示询问的段中的总人数,这个数保持在int以内。
样例
样例输入1
1
10
1 2 3 4 5 6 7 8 9 10
Query 1 3
Add 3 6
Query 2 7
Sub 10 2
Add 6 3
Query 3 10
End
样例输出1
Case 1:
6
33
59
AC code
#include <bits/stdc++.h>
using namespace std;
int N, num, a, c[500020];
inline int lowbit(int x)
{
return x & (-x);
}
inline void updata(int x, int val)
{
for (int i = x; i <= num; i += lowbit(i))
c[i] += val;
}
inline int sum(int x)
{
int ans = 0;
for (int i = x; i > 0; i -= lowbit(i))
ans += c[i];
return ans;
}
int main()
{
cin >> N;
for (int T = 1; T <= N; T++) {
memset(c, 0, sizeof(c));
cin >> num;
for (int i = 1; i <= num; i++) {
cin >> a;
updata(i, a);
}
string sr;
int b;
cout << "Case " << T << ":\n";
while (1) {
cin >> sr;
if (sr == "End")
break;
cin >> a >> b;
if (sr == "Query")
cout << sum(b) - sum(a - 1) << endl;
if (sr == "Add")
updata(a, b);
if (sr == "Sub")
updata(a, -b);
}
}
return 0;
}
标签:return,树状,int,lowbit,Tidy,Derek,数组,区间,模板
From: https://www.cnblogs.com/liudagou/p/17545674.html