首页 > 其他分享 >「模板」树状数组

「模板」树状数组

时间:2023-07-11 18:55:48浏览次数:34  
标签:return 树状 int lowbit Tidy Derek 数组 区间 模板

引入

题目描述

给定\(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

相关文章

  • 自用模板
    #pragmaGCCoptimize(2)#include<bits/stdc++.h>#include<iostream>#include<vector>#include<algorithm>#include<set>#include<utility>#include<string.h>#include<ext/rope>#include<queue>#include&l......
  • 业务系统常规部署交接模板
    1总体情况ip应用192.168.1.1前端1192.168.1.2后端1......1.1前端1#1.进程查看#2.服务路径以及启停#3.版本更新#4.日志查看#5.配置文件说明1.2后端1#1.进程查看#2.服务路径以及启停#3.版本更新#4.日志查看......
  • 动态数组和C++ std::vector详解
    目录1.std::vector2.vector的用法    2.1vector的定义和声明    2.2成员函数        2.2.1基本函数            operator=            assign            get_allocator        2.2.2元素访问   ......
  • 代码随想录算法训练营第二十九天| 1005.K次取反后最大化的数组和 134. 加油站 135. 分
      860.柠檬水找零 思路:遇到20,先给10和5,再给三个5代码:1boollemonadeChange(vector<int>&bills){2if(bills.size()==0)returntrue;34map<int,int>currentMoney;5for(inti=0;i<bills.size();i++)6{7if......
  • vue3中父组件与组件之间参数传递,使用(defineProps/defineEmits),涉及属性传递,对象传递,
    Vue3中子父组件之间的通信一、父组件传递参数到子组件采用defineProps传递属性父组件:<template><div><h1>这是父组件</h1><h1>父组件像子组件传递参数</h1><h2>传递属性值</h2><HH:fatherMessage="fatherMessage":valNum="valNum":valBool=......
  • 【模板】并查集
    简介并查集是什么并查集,在一些有N个元素的集合应用问题中,我们通常是在开始时让每个元素构成一个单元素的集合,然后按一定顺序将属于同一组的元素所在的集合合并,其间要反复查找一个元素在哪个集合中。并查集其实就是一个树,如果要合并的话就将其中一个的根节点连接到另外一个的根......
  • 微信小程序(三)列表渲染&数据绑定&事件绑定&路由跳转&生命周期&本地存储&模板使用
    这里新建个页面log,然后用这个页面进行测试。同时修改app.json,将log页面设置为首页"pages":["pages/index/index","pages/log/log"],"entryPagePath":"pages/log/log",0.数据绑定0.简单的绑定wxml用{{val}}取变量<!--pages/log/lo......
  • 浮点数二分模板
    题目给定一个浮点数$n$,求它的三次方根。输入格式共一行,包含一个浮点数$n$。输出格式共一行,包含一个浮点数,表示问题的解。注意,结果保留$6$位小数。数据范围$−10000≤n≤10000$输入样例:$1000.00$输出样例:$10.000000$思路浮点数二分可以直接分,无需考虑边界情况......
  • 根据模板动态生成word(二)使用poi生成word
    @目录一、准备模板1、创建模板文件二、代码实践1、引入依赖2、自定义XWPFDocument2、公用的方法和变量3、工具类引用的包名4、段落文本替换5、图片替换6、表格替换7、完整的工具类代码三、验证模板生成1、测试代码2、生成效果四、总结一、准备模板1、创建模板文件创建一个word......
  • JAVA集成velocity实现对已有模板替换(占位符变量)替换
      平时我们如果有一些简单的模板替换需求,比如有个txt文件,或者代码生成模板文件要根据传入的变量替换成具体的值就可以使用这个框架 依赖<dependency><groupId>org.apache.velocity</groupId><artifactId>velocity-engine-core</artifactId>......