数据结构-树状数组

news/2024/5/26 21:12:14/文章来源:https://blog.csdn.net/weixin_61494821/article/details/136528964

📑前言

本文主要是【树状数组】——树状数组简单使用的文章,如果有什么需要改进的地方还请大佬指出⛺️

🎬作者简介:大家好,我是听风与他🥇
☁️博客首页:CSDN主页听风与他
🌄每日一句:狠狠沉淀,顶峰相见

目录

    • 📑前言
    • 树状数组模板示例
      • 模板代码:
      • 1208.小球与盒子
    • 📑文章末尾

树状数组模板示例

  • 以1–8为例,构建树状数组
    在这里插入图片描述
我们知道lowbit的性质是,奇数等于12的次方等于本身,偶数为第一次出现的0,如4100lowbit(4)=4
A数组和C数组之间的关系为
C1=A1
C2=A1+A2
C3=A3
C4=A1+A2+A3+A4
C5=A5
C6=A5+A6
C7=A7
C8=A1+A2+A3+A4+A5+A6+A7+A8

模板代码:

package 难点攻克;import java.util.Arrays;public class TreeArray {static int[] A;//原始的数据static int[] C;//树状数组static int n;//数组的元素个数public TreeArray(int[] A) {this.A=new int[A.length];n = A.length;C = new int[n+1];//c[0]不用for(int i=1;i<=A.length;i++) {update(i, A[i-1]);}}public static int lowbit(int x) {return x&(-x);}public static void update(int i,int val) {  //原来的值A[i-1],现在的值是valSystem.out.println("val:"+val+" i:"+A[i-1]);int data = val-A[i-1];//新旧值之间的差距
//		System.out.println("data:"+data);A[i-1]=val;//将A的第i个元素(生活中,计算机里面i-1)修改新的值valfor(int pos=i;pos<=n;pos=pos+lowbit(pos)) {C[pos] += data;}}public static int sumRange(int start,int end) {if(start<1 || start>n || end<1 ||end>n) {return -1;}else {return sum02k(end)-sum02k(start-1);}//sum02k(end)=A1+A2+...+Astart-1 + Astart +...+Aend//sum02k(end)=A1+A2+...+Astart-1}public static int sum02k(int pos) {//c[pos]+c[pos-lowbit[pos]]+...int sum = 0;for(int i=pos;i>=1;i=i-lowbit(i)) {sum=sum+C[i];}//sum(A(1)->A(7)) =>c[7]+C[7-lowbit[7])+c[6-lowbit(6))=c7+c6+c4return sum;}public static void main(String[] args) {// TODO Auto-generated method stubint[] a = {1,2,3,4,5,6,7,8};TreeArray t = new TreeArray(a);System.out.println(Arrays.toString(t.C));t.update(3, 99);System.out.println(Arrays.toString(t.A));System.out.println(Arrays.toString(t.C));System.out.println("前2个的和:"+t.sum02k(2));System.out.println("前6个的和:"+t.sum02k(6));System.out.println("2-6个的和:"+t.sumRange(2, 6));}}

1208.小球与盒子

package 难点攻克;import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.Arrays;public class Main {static long[] A;static long[] C;static int n;public Main(long[] A) {this.A = new long[A.length];n = A.length;C = new long[n+1];for(int i=1;i<=n;i++) {update(i, A[i-1]);}}public static int lowbit(int x) {return x&(-x);}public static void update(int i,long val) {long data = val;A[i-1]=val;for(int pos=i;pos<=n;pos=pos+lowbit(pos)) {C[pos]+=data;}}public static long sum02k(int i) {long ans = 0;for(int pos=i;pos>=1;pos=pos-lowbit(pos)) {ans+=C[pos];}return ans;}public static long Sum(int start,int end) {return sum02k(end)-sum02k(start-1);}public static void main(String[] args) throws IOException {// TODO Auto-generated method stubStreamTokenizer sc = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));sc.nextToken();int n = (int)sc.nval;long nums[] = new long[n];Main t = new Main(nums);sc.nextToken();int m =(int)sc.nval;while(m-->0) {sc.nextToken();int op=(int)sc.nval;sc.nextToken();int x=(int)sc.nval;sc.nextToken();int y=(int)sc.nval;if(op==1) {update(x, y);}else {System.out.println(Sum(x, y));}}}}

📑文章末尾

在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_1007276.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

VR数字展厅在企业中应用的优势有哪些?

随着VR全景技术的成熟&#xff0c;VR数字展厅逐渐成为了企业展示形象和产品的重要手段之一。VR企业数字展厅是一种通过VR技术、3D建模技术展示企业形象和产品的创新方式&#xff0c;将企业线下的展厅搬到线上&#xff0c;为企业品牌形象带来了很多优势。 VR数字展厅在企业中应用…

【大厂AI课学习笔记NO.68】开源和开源发展情况

开源即源代码公开&#xff0c;任何人能获取源代码&#xff0c;查看、修改、分发他们认为合适的代码。 依托同行评审和社区生成&#xff0c;旨在以分散、协作的方式开发。 我们曾经很详细的讨论过开源协议的问题&#xff0c;详细可以参考我的文章&#xff1a; https://giszz.…

为什么要用scrapy爬虫库?而不是纯python进行爬虫?

为什么要用scrapy爬虫库&#xff1f;而不是纯python进行爬虫&#xff1f; Scrapy的优点Scrapy节省的工作使用纯Python编写爬虫的不足 Scrapy是一个使用Python编写的开源和协作的web爬虫框架&#xff0c;它被设计用于爬取网页数据并从中提取结构化数据。Scrapy的强大之处在于其广…

新手如何快速上手学习单片机?

读者朋友能容我&#xff0c;不使博文负真心 新开专栏&#xff0c;期待与诸君共享精彩 个人主页&#xff1a;17_Kevin-CSDN博客 专栏&#xff1a;《单片机》 学习单片机是一个有趣且有挑战性的过程。单片机是一种微控制器&#xff0c;广泛应用于各种电子设备和嵌入式系统中。在这…

精通Linuxd磁盘分区挂载的精髓:从理论到实战一网打尽

前言 想要深入了解Linux系统中磁盘分区挂载的原理和操作步骤吗&#xff1f;这篇文章将为你揭开分区挂载的神秘面纱&#xff0c;从理论到实践&#xff0c;详细讲解分区挂载的一切。无论你是初学者还是有一定经验的用户&#xff0c;都能从中获取新知识&#xff0c;提升技能水平。…

前后端交互理解 简易表白墙(servlet)

前后端交互理解 简易表白墙&#xff08;servlet&#xff09; 文章目录 前后端交互理解 简易表白墙&#xff08;servlet&#xff09;后端核心内容前后端交互接口约定后端代码展示 上期介绍过 Servlet API &#xff0c;本篇文章目的是借助 servlet 做出一个完整的网站。在一个网站…

RabbitMQ应用场景

1、异步处理 假设想象一下我们做一个商城项目&#xff0c;在用户支付模块中&#xff0c;可能会涉及到其它业务&#xff0c;比如&#xff1a;积分折扣、消费券、短信验证等功能。我们传统的执行步骤是逐步执行&#xff0c;也就是说当用户点击支付 ----> 积分折扣 ----> 消…

Docker进阶:深入了解 Dockerfile

Docker进阶&#xff1a;深入了解 Dockerfile 一、Dockerfile 概述二、Dockerfile 优点三、Dockerfile 编写规则四、Dockerfile 中常用的指令1、FROM2、LABEL3、RUN4、CMD5、ENTRYPOINT6、COPY7、ADD8、WORKDIR9、 ENV10、EXPOSE11、VOLUME12、USER13、注释14、ONBUILD 命令15、…

区块链基础知识(上):区块链基本原理、加密哈希、公钥加密

目录 基本原理 加密哈希&#xff1a; 公钥加密&#xff1a; 希望有人向你发送只有你才能打开的加密文档/消息时使用 PKC 希望向其他人发送加密文档/消息并证明它确实由你发送时使用 PKC 使用 PKC 和加密哈希对文档/消息进行数字签名 交易哈希链使用数字签名转让数字资产所…

【洛谷 P8781】[蓝桥杯 2022 省 B] 修剪灌木 题解(模拟+差分)

[蓝桥杯 2022 省 B] 修剪灌木 题目描述 爱丽丝要完成一项修剪灌木的工作。 有 N N N 棵灌木整齐的从左到右排成一排。爱丽丝在每天傍晩会修剪一棵灌木&#xff0c;让灌木的高度变为 0 0 0 厘米。爱丽丝修剪灌木的顺序是从最左侧的灌木开始&#xff0c;每天向右修剪一棵灌木…

centos 系统 yum 无法安装(换国内镜像地下)

centos 系统 yum 因为无法连接到国外的官网而无法安装&#xff0c;问题如下图&#xff1a; 更换阿里镜像&#xff0c;配置文件路径&#xff1a;/etc/yum.repos.d/CentOS-Base.repo&#xff08;如果目录有多余的文件可以移动到子目录&#xff0c;以免造成影响&#xff09; bas…

docker使用jupyter/datascience-notebook,重置密码,并且设置各类易用参数

前言 前一篇文章写了自己安装conda环境&#xff0c;然后添加C、C语言环境等&#xff0c;那时候就在想&#xff0c;有没有现成的docker可以用&#xff0c;后来搜了一下docker的网上镜像&#xff0c;还真的有&#xff1a; 可以看到有一个人的镜像&#xff0c;星星是最多的&#x…

React-嵌套路由

1.概念 说明&#xff1a;在一级路由中又内嵌了其他路由&#xff0c;这种关系就叫做嵌套路由&#xff0c;嵌套至一级路由内的路由又称作二级路由。 2.实现步骤 说明&#xff1a;使用childen属性配置路由嵌套关系&#xff0c;使用<Outlet/>组件配置二级路由渲染的位置。…

基于springboot实现驾校信息管理系统项目【项目源码+论文说明】

基于springboot实现驾校信息管理系统演示 摘要 随着人们生活水平的不断提高&#xff0c;出行方式多样化&#xff0c;也以私家车为主&#xff0c;那么既然私家车的需求不断增长&#xff0c;那么基于驾校的考核管理也就不断增强&#xff0c;那么业务系统也就慢慢的随之加大。信息…

[保姆级教程]Windows安装MongoDB教程

文章目录 导文MongoDB安装包下载1.点击进入mongodb官网2.点击MongoDB Community Edition&#xff08;社区版&#xff09;&#xff0c;进入下图界面3.选择版本4.下载5.安装6.勾选同意协议&#xff0c;点击“Next"7.选择自定义安装8.点击“Next"9.修改到合适的地址10.点…

Tensorflow实现手写数字识别

模型架构 具有10个神经元&#xff0c;对应10个类别&#xff08;0-9的数字&#xff09;。使用softmax激活函数&#xff0c;对多分类问题进行概率归一化。输出层 (Dense):具有64个神经元。激活函数为ReLU。全连接层 (Dense):将二维数据展平成一维&#xff0c;为全连接层做准备。展…

深入了解volatile、内存屏障与happens-before规则

1、编译器优化的重排序。编译器在不改变单线程程序语义的前提下&#xff0c;可以重新安排语句的执行顺序&#xff1b;2、指令级并行的重排序。现代处理器采用了指令级并行技术来将多条指令重叠执行。如果不存在数据依赖性&#xff0c;处理器可以改变语句对应机器指令的执行顺序…

开源的python 游戏开发库介绍

本文将为您详细讲解开源的 Python 游戏开发库&#xff0c;以及它们的特点、区别和应用场景。Python 社区提供了多种游戏开发库&#xff0c;这些库可以帮助您在 Python 应用程序中实现游戏逻辑、图形渲染、声音处理等功能。 1. Pygame 特点 - 基于 Python 的游戏开发库。…

Python实时追踪关键点组成人体模型

项目背景 最近遇到这样一个需求&#xff1a; 1&#xff1a;实时追踪关键点组成人体模型&#xff08;手臂包括三个点&#xff1a;手腕&#xff0c;肘关节&#xff0c;双肩&#xff1b;腿部包括胯骨&#xff0c;膝盖&#xff0c;脚踝&#xff09; 2&#xff1a;运用追踪到的关键…

智慧城市与智慧乡村:共创城乡一体化新局面

一、引言 随着科技的不断进步和城乡发展的日益融合&#xff0c;智慧城市与智慧乡村的建设已成为推动城乡一体化发展的新引擎。智慧城市利用物联网、大数据、云计算等先进技术&#xff0c;实现城市治理、公共服务、产业发展等领域的智能化&#xff1b;而智慧乡村则借助现代科技…