P3374 (树状数组1)

· · 个人记录

思路

题意要求给出一个数列，实现以下操作：

对于单个操作，我们可以使用差分和前缀和，这样可以实现一个操作 O(1) ，另外一个操作 O(n) ，可是两个操作一起上，时间会变成 O(n^2) 了，显然会炸。

所以说我们需要用一个算法来达到 2 个操作之间的平衡，以 O(n\log_n) 的时间复杂度通过这题。

所以说我们需要一个数据结构，以实现区间查询和单点修改的功能。

现在来思考如何实现。

数据结构：

考虑建立一种数据结构，使其可以实现对区间加和的查询和对单个节点的修改。

有一种思路，我们可以构造一颗二叉树，其叶子结点即为其原来数组的值。

再往上走，每两个子结点所对的父节点即为其加和，这样即可实现查询一个节点就实现区间查询。

此时进行优化，由于父节点和左子节可以推出其右子节点，所以我们可以砍去右子节点，此时空间降为 \log_n 。

对于单点修改，只需要对该节点所联系的节点依次加上（或者减去）一个值即可。

这种数据结构叫做树状数组。

这是一个树状数组的概念图

lowbit

实现树状数组，我们应该思考应该如何查询其节点，lowbit(x) 函数用于获取 ( x ) 的二进制表示中最低位的 1 所对应的值。例如，lowbit(6) 返回 2，因为 6 的二进制是 110，最低位的 1 对应的值是 10（即 2）,借此我们可以表示出每一个节点。

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

add

对于添加值，我们需要给每一个节点加上这个值，即可视为添加一个节点，从下到上，依次加。

get

对于得到区间和，从上到下，加上每一个值即可。

由于 get(x) 求出的是一到 x 的区间和，所以说这里要用 get(y)-get(x-1) 得到 x 到 y 区间之和。

code:

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
int a[8000001];
int c[2000001];
int lowbit(int x){
    return x&(-x);
} 
void add(int x,int k){
    while(x<=n){
        c[x]+=k;
        x+=lowbit(x);
    }
}
int get(int x){
    int ans=0;
    while(x>0){
        ans+=c[x];
        x-=lowbit(x);
    }
    return ans;
}
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];  
        add(i,a[i]);    
    }
    for(int i=1;i<=m;i++){
        int opt;
        cin>>opt;
        int x,y;
        cin>>x>>y;
        if(opt==1){
            add(x,y);
        } 
        else{
            if(y<x) swap(x,y);
            cout<<get(y)-get(x-1)<<endl;
        }
    }
    return 0;
}