树状数组笔记

本文主要是介绍树状数组笔记，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

lowbit：保留数在2进制下最后一个1，前面全变0

模板1：单点修改，区间查询

例题：Problem - 1679C - Codeforces

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<ctype.h>
#include<iostream>
#include<algorithm>
#include<queue> 
typedef long long ll;
using namespace std;
int col[200005],row[200009];
int dc[200009],dr[200009];
int n,q;
int lowbit(int x){
    return x&(-x);
}
int query(int x,int k[]){
    int s=0;
    for(;x;x-=lowbit(x)) s+=k[x];
    return s;
}
void modify(int x,int s,int k[]){
    for(;x<=n;x+=lowbit(x)) k[x]+=s;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0),std::cout.tie(0);
    cin>>n>>q;
    for(int i=0;i<q;i++){
        int t;cin>>t;
        if(t==1){
            int x,y;cin>>x>>y;
            if(!dc[x])
            modify(x,1,col);
            if(!dr[y])
            modify(y,1,row);
            dc[x]++,dr[y]++;
        }
        else if(t==2){
            int x,y;cin>>x>>y;
            dc[x]--,dr[y]--;
            if(!dc[x])modify(x,-1,col);
            if(!dr[y])modify(y,-1,row);
            
        }
        else{
            int x1,x2,y1,y2;cin>>x1>>y1>>x2>>y2;
            if(x2-x1+1==query(x2,col)-query(x1-1,col)||y2-y1+1==query(y2,row)-query(y1-1,row))
                cout<<"Yes\n";
            else
                cout<<"No\n";
        }
    }
}

这篇关于树状数组笔记的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！