首页 > 其他分享 >树状数组

树状数组

时间:2023-06-25 10:22:05浏览次数:48  
标签:树状 int lowbit while long add maxn 数组

维护时间复杂度 O(nlogn)

查询时间复杂度 O(logn)

优点:好写

缺点 fw没啥用

主要就是用一个叫lowbit的东西来实现用一个树状的东西维护区间和等,其实只要记住修改的时候+=lowbit(x),查询的时候-=lowbit(x)就行了

1.板子

这个应该都会吧qwq

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
const int maxn=1e6+5;
int num[maxn];
int c[maxn];
int lowbit(int a){
return(a&-a);
}
int ask(int x){
	int res=0;
	while(x){
		res+=c[x];
		x-=lowbit(x);
	}
	return res;
}
void add(int x,int v){
	while(x<=n){
		c[x]+=v;
		x+=lowbit(x);
	}
	return;
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>num[i];
		add(i,num[i]);
	}
	for(int i=1;i<=m;i++){
		int a,b,c;
		cin>>a>>b>>c;
		if(a==1){
			add(b,c);
		}
		if(a==2){
			cout<<ask(c)-ask(b-1)<<endl;
		}
	}
	return 0;
}

2.区间修改区间查询

这个要用到差分,下面用di表示

转移式 Σ(1,n) ai=Σ(1,n) di(n+1)-dii

ybtoj树状数组例四

代码:

#include <bits/stdc++.h>
#define int long long

using namespace std;
const int maxn = 2e6 + 5;
int n, m;
int sum[maxn];
int sum2[maxn];
int a[maxn];
int b[maxn];
int lowbit(int x) { return x & -x; }
void add(int x, int v, int t) {
    if (t == 1) {
        while (x <= n) {
            sum[x] += v;
            x += lowbit(x);
        }
    } else {
        while (x <= n) {
            sum2[x] += v;
            x += lowbit(x);
        }
    }
}
int ask(int x, int t) {
    int res = 0;
    if (t == 1) {
        while (x) {
            res += sum[x];
            x -= lowbit(x);
        }
    } else {
        while (x) {
            res += sum2[x];
            x -= lowbit(x);
        }
    }
    return res;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    int lst = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        add(i, a[i] - lst, 1);
        add(i, (i - 1) * (a[i] - lst), 2);
        lst = a[i];
    }
    for (int ii = 1; ii <= m; ii++) {
        int co;
        cin >> co;
        if (co == 1) {
            int x, y, k;
            cin >> x >> y >> k;
            add(x, k, 1);
            add(y + 1, -k, 1);
            add(x, (x - 1) * k, 2);
            add(y + 1, -y * k, 2);
        } else {
            int x, y;
            cin >> x >> y;
            cout << ask(y, 1) * y - ask(y, 2) - ask(x - 1, 1) * (x - 1) + ask(x - 1, 2) << endl;
        }
    }
    return 0;
}

3.矩阵修改矩阵查询

转移式 Σ(1,n)Σ(1,m) aij= Σ(1,n)Σ(1,m) ((n+1)(m+1))dij-(m+1)diji-(n+1)dijj+dijij)

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=2e3+50;
int t[maxn][maxn],ti[maxn][maxn],tj[maxn][maxn],tij[maxn][maxn];
int n,m;
int lowbit(int x){
	return x&-x;
}
void add(int x,int y,int k){
	int prey=y;
	int prex=x;
	while(x<=n){
		y=prey;
		while(y<=m){
			t[x][y]+=k;
			ti[x][y]+=prex*k;
			tj[x][y]+=prey*k;
			tij[x][y]+=prex*prey*k;
			y+=lowbit(y);
		}
		x+=lowbit(x);
	}
}
int ask(int x,int y){
	int prey=y;
	int prex=x;
	int res=0;
	while(x){
		y=prey;
		while(y){
			res+=(prex+1)*(prey+1)*t[x][y]-ti[x][y]*(prey+1)-tj[x][y]*(prex+1)+tij[x][y];
			y-=lowbit(y);			
		}
		x-=lowbit(x);
	}
	return res;
} 
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	int opt;
	while(cin>>opt){
		int x,y,xx,yy;
		 cin>>x>>y>>xx>>yy;
		 if(opt==1){
		 	int k;
		 	cin>>k;
		 	add(x,y,k);
		 	add(x,yy+1,-k);
		 	add(xx+1,y,-k);
		 	add(xx+1,yy+1,k);
		 }
		 else{
//		 	cout<<ask(xx,yy)<<" "<<ask(x-1,y-1)<<" "<<ask(xx,y-1)<<" "<<ask(x-1,yy)<<endl;
		 	cout<<ask(xx,yy)+ask(x-1,y-1)-ask(xx,y-1)-ask(x-1,yy)<<endl;
		 }
	}
	return 0;
}

完结

标签:树状,int,lowbit,while,long,add,maxn,数组
From: https://www.cnblogs.com/jt0007/p/17502202.html

相关文章

  • C语言中将二维数组作为函数参数来传递
    C语言中经常需要通过函数传递二维数组,有三种方法可以实现,如下:方法一,形参给出第二维的长度#include<stdio.h>voidfunc(intn,charstr[][5]){inti;for(i=0;i<n;i++)printf("/nstr[%d]=%s/n",i,str[i]);}voidmain(){char*p[3];charstr[]......
  • 【js学习笔记四】数组双重去重的方式三filter
     目录前言导语运行结果总结前言   我是歌谣我有个兄弟巅峰的时候排名c站总榜19叫前端小歌谣曾经我花了三年的时间创作了他现在我要用五年的时间超越他今天又是接近兄弟的一天人生难免坎坷大不了从头再来歌谣的意志是永恒的放弃很容易但是坚持一定很酷导语   数组......
  • 【js学习笔记五】数组双重去重的方式四先排序在对比
     目录前言导语 代码部分运行结果总结前言   我是歌谣我有个兄弟巅峰的时候排名c站总榜19叫前端小歌谣曾经我花了三年的时间创作了他现在我要用五年的时间超越他今天又是接近兄弟的一天人生难免坎坷大不了从头再来歌谣的意志是永恒的放弃很容易但是坚持一定很酷导语......
  • 【LeetCode摩尔投票】有趣的简单题:数组中出现次数超过一半的数字
    数组中出现次数超过一半的数字https://leetcode.cn/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。你可以假设数组是非空的,并且给定的数组总是存在多数元素。示例1:输入:[1,2,3,......
  • Java 一维数组的使用
    Java一维数组的使用1.一维数组的定义在不知道数组内容可以直接使用下面的定义方法:int[]arr=newint[数组个数];或intarr[]=newint[数组个数];在知道数组内容可以使用如下:int[]arr={data1,data2,data.....};2.数组的传递数组的传递与其他基本类型的值传递不同,......
  • c语言-字符串+转义字符+注释、语句、函数、数组、操作符 2
    一、字符串+转义字符+注释字符串类型(相较于字符数据类型):eg:“”;//空字符串定义:由双引号引起的一串字符为字符串字面值,简称字符串。(后面默认会有\0,结束标志不算内容intmain(){chararr1[]="abc";//数组//"abc"——'a''b''c''\0'——'\0'......
  • 【剑指Offer】40、数组中只出现一次的数字
    【剑指Offer】40、数组中只出现一次的数字题目描述:一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度为O(n),空间复杂度为O(1)。解题思路:这道题目相对比较难,一般情况下,我们首先可以想到的是顺序扫描数组,但其时间复杂......
  • 二维数组的传参方式
    1.传数组整体格式:(1)给函数传参时,用数组名arr;(2)函数定义时,用intarr[3][5]接收;(3)在函数中打印元素时,用arr[1][1]。voidtest(intarr[3][5]){ printf("%d",arr[1][1]);}intmain(){ intarr[3][5]={{1,2,3,4,5},{2,3,4,5,6},{3,4,5,6,7}}; test(arr); return0;}2.传首元......
  • 【js学习笔记三】数组去重的第二种方式indexof
     目录前言导语代码部分 运行结果总结前言   我是歌谣我有个兄弟巅峰的时候排名c站总榜19叫前端小歌谣曾经我花了三年的时间创作了他现在我要用五年的时间超越他今天又是接近兄弟的一天人生难免坎坷大不了从头再来歌谣的意志是永恒的放弃很容易但是坚持一定很酷导语......
  • 后缀数组
    ......