IndexTree

简介: IndexTree

IndexTree解决的问题

在这里插入图片描述

线段树支持区间更新,但是IndexTree只支持单点更新。

假设给定一个数组,如果频繁的要求某个范围的累加和,在原数组不变的情况下,可以申请一个辅助数组做前缀和(help),然后只需要在辅助数组查询两次就可以得到某个范围上的累加和了!

但是,如果原数组某个变动了的话,前缀和就无法实现了

所以要用到IndexTree,下图表示help数组每个位置记录原数组哪些范围,比如:1位置记录的是原数组1到1位置上的累加和、2位置记录的是原数组1到2位置上的累加和...

help数组不是上面提到的前缀和数组!!!

在这里插入图片描述

两个规律

第一个:假设某一个index的二进制表示形式如下,index为help数组中的下标i,那么index位置的值表示记录原数组哪些范围的值呢?010110001 ~ 010111000
在这里插入图片描述
举例
在这里插入图片描述
在这里插入图片描述
第二个:如果想求原数组中从 1 ~ i 位置的前缀和,假设 i 为33,如何利用help数组求?
在这里插入图片描述
i 转换为二进制形式,33位置上只管自己,但是32位置上管的是从1到32位置上的所有,所以它两一累加就实现了1到33的累加
在这里插入图片描述
假设要求原数组中从1到index位置的累加和(index等于52,index的二进制是 0110100),如何利用help数组求?

help[0110100] + help[0110000] + help[0100000]

那么help数组中index位置上管的是原数组中哪些范围的值呢?

help[0110100] = help[0110001] ~ help[0110100]
help[0110000] = help[0100001] ~ help[0110000]
help[0100000] = help[0000001] ~ help[0100000]

仔细看上面红色加粗字体(从下往上看),是不是就是连起来了呢,所以原数组中从1到index位置的累加和就这样利用help数组求出来了

在这里插入图片描述

add方法

假设原数组中3位置的值发生了变化,那么如何知道help数组中哪些位置的值也发生了变化呢?
在这里插入图片描述
将3化为二进制形式后,提取出最右侧的1再加上自己,

011 -> 100 -> 1000 -> 10000...,那么在help数组中,这些位置的数都随之发生改动。
在这里插入图片描述

时间复杂度

O(logN),因为是在位信息上操作,有几个位信息就做几次操作,位数就是logN次

总结

一维IndexTree很容易的实现了单点更新和 1 ~ index位置上的前缀和,

如何实现任意一个范围 L到R的前缀和呢?

稍微一加工就可以了:1到R 减去 1到L-1 就实现了

问题是这些功能线段树也可以实现,并且时间复杂度都一样,那么IndexTree存在的意义是什么呢?

线段树是一维的,推成二维很麻烦,而IndexTree推成二维很容易!!!

代码实现

package com.harrison.class22;

/**
 * @author Harrison
 * @create 2022-04-02-9:39
 * @motto 众里寻他千百度,蓦然回首,那人却在灯火阑珊处。
 */
public class Code01_IndexTree {
    // 下标从1开始
    public static class IndexTree{
        private int[] tree;
        private int N;

        // 0位置弃而不用
        public IndexTree(int size){
            N=size;
            tree=new int[N+1];
        }

        // 1~index累加和是多少
        /*
        补充一个小知识:负数的二进制用其正数的补码形式表示
        补码:反码+1
         */
        public int sum(int index){
            int ret=0;
            while(index>0){
                ret+=tree[index];
                index-=index&(-index);// index-=(index & (~index+1))
            }
            return ret;
        }

        // index & -index : 提取出index最右侧的1出来
        // index :           0011001000
        // index & -index :  0000001000
        public void add(int index,int d){
            while(index<=N){
                tree[index]+=d;
                index+=index&(-index);
            }
        }
    }

    public static class Right{
        private int[] nums;
        private int N;

        public Right(int size){
            N=size+1;
            nums=new int[N+1];
        }

        public int sum(int index){
            int ret=0;
            for(int i=1; i<=index; i++){
                ret+=nums[i];
            }
            return ret;
        }

        public void add(int index,int d){
            nums[index]+=d;
        }
    }

    public static void main(String[] args) {
        int N = 100;
        int V = 100;
        int testTime = 2000000;
        IndexTree tree = new IndexTree(N);
        Right test = new Right(N);
        System.out.println("test begin");
        for (int i = 0; i < testTime; i++) {
            int index = (int) (Math.random() * N) + 1;
            if (Math.random() <= 0.5) {
                int add = (int) (Math.random() * V);
                tree.add(index, add);
                test.add(index, add);
            } else {
                if (tree.sum(index) != test.sum(index)) {
                    System.out.println("Oops!");
                }
            }
        }
        System.out.println("test finish");
    }
}
相关文章
|
2月前
|
负载均衡 监控 应用服务中间件
除了 Nginx,还有以下一些常见的负载均衡工具
【10月更文挑战第17天】这些负载均衡工具各有特点和优势,在不同的应用场景中发挥着重要作用。选择合适的负载均衡工具需要综合考虑性能、功能、稳定性、成本等因素。
|
Linux
Xshell 登录 AWS CentOS 出现“所选择的用户秘钥未在远程主机上注册“,最终解决办法!
其实就是 登录用户名错了,是 root,不是centos 也不是 ec2-user !  Xshell 连接配置界面如下   最重要是 登录授权配置  最后,登录成功! 就这么简单
2864 0
|
4月前
Conda 修改下载包路径
Conda 修改下载包路径
127 0
|
7月前
|
算法 测试技术 C#
【模拟】【C++算法】2826. 将三个组排序
【模拟】【C++算法】2826. 将三个组排序
|
网络安全 数据安全/隐私保护
阿里云Permission denied (publickey,gssapi-keyex,gssapi-with-mic)
阿里云Permission denied (publickey,gssapi-keyex,gssapi-with-mic)
385 0
|
6天前
|
调度 云计算 芯片
云超算技术跃进,阿里云牵头制定我国首个云超算国家标准
近日,由阿里云联合中国电子技术标准化研究院主导制定的首个云超算国家标准已完成报批,不久后将正式批准发布。标准规定了云超算服务涉及的云计算基础资源、资源管理、运行和调度等方面的技术要求,为云超算服务产品的设计、实现、应用和选型提供指导,为云超算在HPC应用和用户的大范围采用奠定了基础。
179581 20
|
14天前
|
存储 运维 安全
云上金融量化策略回测方案与最佳实践
2024年11月29日,阿里云在上海举办金融量化策略回测Workshop,汇聚多位行业专家,围绕量化投资的最佳实践、数据隐私安全、量化策略回测方案等议题进行深入探讨。活动特别设计了动手实践环节,帮助参会者亲身体验阿里云产品功能,涵盖EHPC量化回测和Argo Workflows量化回测两大主题,旨在提升量化投研效率与安全性。
云上金融量化策略回测方案与最佳实践
|
15天前
|
人工智能 自然语言处理 前端开发
从0开始打造一款APP:前端+搭建本机服务,定制暖冬卫衣先到先得
通义灵码携手科技博主@玺哥超carry 打造全网第一个完整的、面向普通人的自然语言编程教程。完全使用 AI,再配合简单易懂的方法,只要你会打字,就能真正做出一个完整的应用。
9342 23
|
19天前
|
Cloud Native Apache 流计算
资料合集|Flink Forward Asia 2024 上海站
Apache Flink 年度技术盛会聚焦“回顾过去,展望未来”,涵盖流式湖仓、流批一体、Data+AI 等八大核心议题,近百家厂商参与,深入探讨前沿技术发展。小松鼠为大家整理了 FFA 2024 演讲 PPT ,可在线阅读和下载。
5002 15
资料合集|Flink Forward Asia 2024 上海站
|
19天前
|
自然语言处理 数据可视化 API
Qwen系列模型+GraphRAG/LightRAG/Kotaemon从0开始构建中医方剂大模型知识图谱问答
本文详细记录了作者在短时间内尝试构建中医药知识图谱的过程,涵盖了GraphRAG、LightRAG和Kotaemon三种图RAG架构的对比与应用。通过实际操作,作者不仅展示了如何利用这些工具构建知识图谱,还指出了每种工具的优势和局限性。尽管初步构建的知识图谱在数据处理、实体识别和关系抽取等方面存在不足,但为后续的优化和改进提供了宝贵的经验和方向。此外,文章强调了知识图谱构建不仅仅是技术问题,还需要深入整合领域知识和满足用户需求,体现了跨学科合作的重要性。