首页 > 编程语言 >树状数组详解!(C++_单点/区间查询_单点/区间修改)

树状数组详解!(C++_单点/区间查询_单点/区间修改)

时间:2023-06-20 15:05:22浏览次数:61  
标签:单点 树状 int C++ 查询 add 数组 区间


先把这张著名的树状数组结构图摆在最前面,接下来我们就以这张图讲起!

树状数组详解!(C++_单点/区间查询_单点/区间修改)_树状数组


       首先图中的A数组就是所谓的原数组,也就是普通的数组形态,C则是我们今天要说的树状数组(可以看出一个树的形状,但其实和树没多大关系)

从图中可以明显看到以下几个式子:

树状数组详解!(C++_单点/区间查询_单点/区间修改)_前缀和_02

树状数组详解!(C++_单点/区间查询_单点/区间修改)_前缀和_03

树状数组详解!(C++_单点/区间查询_单点/区间修改)_树状数组_04

树状数组详解!(C++_单点/区间查询_单点/区间修改)_前缀和_05

树状数组详解!(C++_单点/区间查询_单点/区间修改)_前缀和_06

树状数组详解!(C++_单点/区间查询_单点/区间修改)_前缀和_07

树状数组详解!(C++_单点/区间查询_单点/区间修改)_数组_08

树状数组详解!(C++_单点/区间查询_单点/区间修改)_前缀和_09

有点像前缀和不是?

但这样还看不出什么整体规律,所以我们再来变一下,把十进制编程变成二进制:

树状数组详解!(C++_单点/区间查询_单点/区间修改)_树状数组_10

树状数组详解!(C++_单点/区间查询_单点/区间修改)_前缀和_11

树状数组详解!(C++_单点/区间查询_单点/区间修改)_树状数组_12

树状数组详解!(C++_单点/区间查询_单点/区间修改)_树状数组_13

树状数组详解!(C++_单点/区间查询_单点/区间修改)_数组_14

树状数组详解!(C++_单点/区间查询_单点/区间修改)_数组_15

树状数组详解!(C++_单点/区间查询_单点/区间修改)_数组_16

树状数组详解!(C++_单点/区间查询_单点/区间修改)_树状数组_17

这下有没有找到规律呢?

注意观察C数组的二进制的最低位的1的位置。你会发现:将每一个二进制,去掉所有高位1,只留下最低位的1,然后从那个数一直加到1

在程序中如何实现去掉所有高位的1呢?

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

lowbit()函数一知半解请的看这里:

负数的补码等于原码加一,正数的补码和原码相等。运用这个特性,将两者进行与运算就能知道第一个1的位置了,还是不懂的可以看这个栗子:
6的原码:0110; 6的补码:0110;
-6的反码:1001;(反码等于原码置反)
-6的补码:1010;(补码等于反码加一) (6的补码)&(-6的补码)=0110&1010=0010; 这样就只剩下最低为的1了!

下来正式解释几个常用的树状数组函数:

1.单点修改
void add(int x, int k)
{
    while (x <= n)
    {
        tree[x] += k;
        x += lowbit(x);
    }
}

因为树状数组是牵一发而动全身,所以一直lowbit即可,这个过程正是我之前所模拟的算式。你想啊要是A[1]要加k, 那么是不是后面要用到A[1]的都得加k!就是这个理!

2.区间查询

就是前缀和,比如查询x到y区间的和,那么就将从1到y的和减去从1到x的和。

从1到y的和求法是,将y转为2进制,然后一直减去lowbit(y),一直到0

比如求1到7的和(配合开始那张图理解效果更佳!)
树状数组详解!(C++_单点/区间查询_单点/区间修改)_树状数组_18
树状数组详解!(C++_单点/区间查询_单点/区间修改)_数组_19
树状数组详解!(C++_单点/区间查询_单点/区间修改)_数组_20
树状数组详解!(C++_单点/区间查询_单点/区间修改)_树状数组_21

int sum(int x)
{
    int ans=0;
    while(x!=0)
    {
        ans+=tree[x];
        x-=lowbit(x);
    }
    return ans;
}
3.区间修改&&单点查询

先给代码:

void add(int x, int k)//你没有看错,我和单点修改的代码是一样的!(主函数操作要变,请看下面解释!)
{
    while (x <= n)
    {
        tree[x] += k;
        x += lowbit(x);
    }
}

详细:
       假设我们要修改[x, y]这个区间的数,我们想给这个区间所有的数都加k!那我们是不是可以给从x到n的所有数都加上k, 再给从y+1到n的所有数加上-k!

实际主函数中的操作:

add(x, k);
            add(y + 1, -k);

树状数组详解!(C++_单点/区间查询_单点/区间修改)_前缀和_22树状数组详解!(C++_单点/区间查询_单点/区间修改)_数组_23的所有数都加树状数组详解!(C++_单点/区间查询_单点/区间修改)_前缀和_24,只是给树状数组详解!(C++_单点/区间查询_单点/区间修改)_树状数组_25加了树状数组详解!(C++_单点/区间查询_单点/区间修改)_前缀和_24(当然后面与树状数组详解!(C++_单点/区间查询_单点/区间修改)_树状数组_25有关的也要改),然后再给树状数组详解!(C++_单点/区间查询_单点/区间修改)_树状数组_28加了树状数组详解!(C++_单点/区间查询_单点/区间修改)_树状数组_29(当然后面与C[y-1]有关的也要变),为什么会这样设定呢?按照常规思维的话这样操作会导致中间有的数未加上树状数组详解!(C++_单点/区间查询_单点/区间修改)_前缀和_24,但是存在即合理!因为你要输出的时候是不是要引用树状数组详解!(C++_单点/区间查询_单点/区间修改)_数组_31函数?树状数组详解!(C++_单点/区间查询_单点/区间修改)_数组_31函数是不是会加上之前所有的数?那树状数组详解!(C++_单点/区间查询_单点/区间修改)_前缀和_22树状数组详解!(C++_单点/区间查询_单点/区间修改)_数组_23之间的数是不是最终还是会加上x位置的那个树状数组详解!(C++_单点/区间查询_单点/区间修改)_前缀和_24!!!
       但是这个时候就又发现了一个问题,我想要单点查询怎么办?比如查询x+3这个位置上的数(树状数组详解!(C++_单点/区间查询_单点/区间修改)_数组_36),按照之前区间查询的思想树状数组详解!(C++_单点/区间查询_单点/区间修改)_前缀和_37,那之前操作中要加上去的树状数组详解!(C++_单点/区间查询_单点/区间修改)_前缀和_24怎么办???蛤!所以这里的树状数组就不能加上原数组中的数了,直接在初始时将树状数组全部置零,树状数组中只保存区间修改所操作的值树状数组详解!(C++_单点/区间查询_单点/区间修改)_前缀和_24,这样就可以明目张胆的使用树状数组详解!(C++_单点/区间查询_单点/区间修改)_树状数组_40了,直接从树状数组详解!(C++_单点/区间查询_单点/区间修改)_数组_41加到树状数组详解!(C++_单点/区间查询_单点/区间修改)_数组_42,反正又不会加到多余的数,毕竟原数组和树状数组没关系了嘛,只需要在输出的时候多加上一个原数组的当前的值就好!

比如像这样:

cout << A[x+3] + sum(x+3) << endl;

所以单点查询的代码和区间查询也是一样的,只不过是主函数中的操作稍微变了下~
下面我贴两个模板题,有兴趣的话可以去康康:

P3374 【模板】树状数组 1 (单点修改+区间查询)

Code

#include<bits/stdc++.h>
using namespace std;
int tree[500010];
int n, m;
int lowbit(int x)
{
    return x & -x;
}
void add(int x, int k)
{
    while (x <= n)
    {
        tree[x] += k;
        x += lowbit(x);
    }
}
int sum(int x)
{
    int ans = 0;
    while (x != 0)
    {
        ans += tree[x];
        x -= lowbit(x);
    }
    return ans;
}
int main()
{

    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        int a;
        cin >> a;
        add(i, a);
    }
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        if (u == 1)
            add(v, w);
        else if (u == 2)
            cout << sum(w) - sum(v - 1) << endl;
    }
    return 0;
}

P3368 【模板】树状数组 2 (区间修改+单点查询)

Code

#include<bits/stdc++.h>
using namespace std;
int tree[500010], y[500010];
int n, m;
int lowbit(int x)
{
    return x & -x;
}
void add(int x, int k)
{
    while (x <= n)
    {
        tree[x] += k;
        x += lowbit(x);
    }
}
int sum(int x)
{
    int ans = 0;
    while (x != 0)
    {
        ans += tree[x];
        x -= lowbit(x);
    }
    return ans;
}
int main()
{

    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> y[i];
    for (int i = 1; i <= m; i++)
    {
        int u, a, b, c, v;
        cin >> u;
        if (u == 1)
        {
            cin >> a >> b >> c;
            add(a, c);
            add(b + 1, -c);
        }
        else if (u == 2)
        {
            cin >> v;
            cout << y[v] + sum(v) << endl;
        }
    }
    return 0;
}


标签:单点,树状,int,C++,查询,add,数组,区间
From: https://blog.51cto.com/u_16165815/6522642

相关文章

  • C++用纯虚函数实现协议委托的例子
      C++不像其他很多编程语言有接口、委托或者协议的概念,但是利用纯虚函数和C++多重继承的特性,我们也能实现接口、委托或协议要做的事情,下面的通过一个人设置闹钟然后被闹钟唤醒的例子来说明如何在C++中实现委托回调。#include<iostream>#include<unistd.h>usingstd::cout;u......
  • C++ 计时方法 std::chrono
    计时的作用:测试某一段代码的运行时间,时间越短,则性能相对越高。C++11标准的”最佳计时方法“的代码:1#include<chrono>2usingnamespacestd;3usingnamespacechrono;45autostart=system_clock::now();6//dosomething...7autoend=system_clock::no......
  • C++ 计时器:chrono库介绍
    C++11有了chrono库,可以在不同系统中很容易的实现定时功能。要使用chrono库,需要#include,其所有实现均在std::chrononamespace下。注意标准库里面的每个命名空间代表了一个独立的概念。chrono是一个模版库,使用简单,功能强大,只需要理解三个概念:duration、time_point、clock一、时......
  • 【剑指 Offer】数组中重复的数字(C++_Easy_遍历/哈希/快排/原地)
    题目在一个长度为n的数组nums里的所有数字都在0~n-1的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。测试样例输入:[2,3,1,0,2,5,3]输出:2或3限制2<=n<=100000题解题解一:遍历对vector容器......
  • 【计算机算法设计与分析】线性时间选择(C++_分治递归)
    问题描述给定线性序集中n个元素和一个整数k,1≤k≤n,要求找出这n个元素中第k小的元素。思路线性时间选择有两种方法:(1)随机选择快排的标准元素。(2)将集合分为n个由五个元素组成的集合,对每个五元素集合求其中位数,再对所有的五元素集合的中位数求其中位数,作为快排的标准元素。CodeV-1(Ran......
  • 【剑指 Offer】用两个栈实现队列(C++_Easy_栈/队列)
    1.题目用两个栈实现一个队列。队列的声明如下,请实现它的两个函数appendTail和deleteHead,分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素,deleteHead操作返回-1)2.示例2.1示例1输入:[“CQueue”,“appendTail”,“deleteHead”,“deleteHead”......
  • 【计算机算法设计与分析】6-5 最小重量机器设计问题(C++_回溯法/分支限界法)
    问题描述设某一机器由n个部件组成,每一种部件都可以从m个不同的供应商处购得。设wij是从供应商j处购得的部件i的重量,cij是相应的价格。设计一个优先队列式分支限界法,给出总价格不超过d的最小重量机器设计。对于给定的机器部件重量和机器部件价格,设计一个优先队列式分......
  • 【蓝桥杯_真题演练】换零钞(C++_遍历)
    题目x星球的钞票的面额只有:100元,5元,2元,1元,共4种。小明去x星旅游,他手里只有2张100元的x星币,太不方便,恰好路过x星银行就去换零钱。小明有点强迫症,他坚持要求200元换出的零钞中2元的张数刚好是1元的张数的10倍,剩下的当然都是5元面额的。银行的工作人员有点为难,你能帮助算出:在满足小......
  • 【蓝桥杯_真题演练】第九届C/C++省赛B组_C-乘积尾零(C++_数论)
    Problem如下的10行数据,每行有10个整数,请你求出它们的乘积的末尾有多少个零?56504542355447394641143871907390432927587949611356595245743230514434670435949937117368663397475975573070228714539899148657223135117040145510512072928809......
  • PTA_乙级_1015 德才论(C++_模拟_快排)
    宋代史学家司马光在《资治通鉴》中有一段著名的“德才论”:“是故才德全尽谓之圣人,才德兼亡谓之愚人,德胜才谓之君子,才胜德谓之小人。凡取人之术,苟不得圣人,君子而与之,与其得小人,不若得愚人。”现给出一批考生的德才分数,请根据司马光的理论给出录取排名。输入格式:输入第一行给出3个......