数组的前缀和及查分数组

数组的前缀和及查分数组1,前缀和主要适用场景是原始数组不会被修改的情况下,频繁查询某个区间的累加和。这里就不写前缀和的代码了,就是用一个数组记录下原有数组的前缀和。比如,prefix[i]就代表着nums[0…i-1]所有元素的累加和,如果我们想求区间nums[i…j]的累加和,只要计算prefix[j+1]-prefix[i]即可,而不需要遍历整个区间求和。(需要注意的是使用场景是频繁查询某个区间的累加和,而不需要对原始数组进行频繁修改)2,查分数组的主要适用场景是**频繁对原始数组的某个区间的元素进行增减。**比

大家好,又见面了,我是你们的朋友全栈君。

1,前缀和主要适用场景是原始数组不会被修改的情况下,频繁查询某个区间的累加和。
这里就不写前缀和的代码了,就是用一个数组记录下原有数组的前缀和。比如,prefix[i]就代表着nums[0…i-1]所有元素的累加和,如果我们想求区间nums[i…j]的累加和,只要计算prefix[j + 1] – prefix[i]即可,而不需要遍历整个区间求和。(需要注意的是使用场景是频繁查询某个区间的累加和,而不需要对原始数组进行频繁修改)
2,查分数组的主要适用场景是**频繁对原始数组的某个区间的元素进行增减。**比如说,给定一个数组nums,要求给区间nums[2…6]全部加1,再给nums[3…9]全部减3,再给nums[0…4]全部加2,等等。当然可以使用for循环挨个处理,但是可以利用查分数组来达到O(1)复杂度就可以完成某个动作。diff[i]就是nums[i]和nums[i – 1]之差。比如:
nums: 8 5 9 6 1
diff: 8 -3 4 -3 -5
首先可以通过这个数组来还原原来的数组,也可以利用O(1)复杂度完成给nums[i…j]全部加val的操作。只需两步即可,第一步:diff[i] += val, 这意味着nums[i…]的值全都加val,第二步:diff[j + 1] -= val(j + 1 < size),这意味着nums[j + 1…]的值全都减val,因为第一步加了。

class Difference{ 
   
    private:
        vector<int> diff;
    public:
        Difference(vector<int>& nums){ 
   
            diff.push_back(nums[0]);

            for(int i = 1; i < nums.size(); i++){ 
   
                diff.push_back(nums[i] - nums[i - 1]);
            }
        }

        void increment(int i, int j, int val){ 
   
            diff[i] += val;
            if(j + 1 < diff.size()){ 
   
                diff[j + 1] -= val;
            }
        }

        vector<int> result(){ 
   
            vector<int> vec;

            vec.push_back(diff[0]);

            for(int i = 1; i < diff.size(); i++){ 
   
                vec.push_back(vec.back() + diff[i]);
            } 

            return vec;
        }
    };
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/131828.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 京东金融大数据竞赛猪脸识别(3)- 图像特征提取之二

    京东金融大数据竞赛猪脸识别(3)- 图像特征提取之二深度网络既然在图像识别方面有很高的准确率,那将某一层网络输出数据作为图像特征也应该是可行的。该程序给出了使用Alexnet第七层作为激活层提取图像特征的示例。代码如下:clear;trainPath=fullfile(pwd,’image’);trainData=imageDatastore(trainPath,…’IncludeSubfolders’,true…

  • 云服务器搭建java服务器运行环境

    云服务器搭建java服务器运行环境文章目录安装jdk解压jdk配置环境变量安装tomcattomcat开机自启安装MySQL安装MySQL开机启动启动mysql服务配置mysql如果运行上面的命令中途发生错误:`ERROR1558(HY000):Columncountofmysql.useriswrong.Expected43,found39.`进入mysql安装jdk先下载jdklinux版本,点…

  • ViewPager 2 使用讲解「建议收藏」

    ViewPager 2 使用讲解「建议收藏」之前早有耳闻Google为我们提供新的控件来替换老旧的ViewPager进而解决一些不好解决的bug问题,巴拉巴拉一大堆,就是前因后果啥的…相信读者已经在“张鸿洋”大神、“郭霖”大神或者是其他Android大佬的公众号那里看见了许许多多了,或许各位感觉很无聊了,笔者菜鸟,分析不了历史背景,也不是很懂源码,但是小菜鸟,可以带给位看官尝个鲜,教你怎么用,怎么上手哈,闲话不多说,我们步入正题。…

  • Task 生成排队人数任务线程

    Task 生成排队人数任务线程Task 生成排队人数任务线程

  • Spark Streaming详解(重点窗口计算)

    Spark Streaming详解(重点窗口计算)前面有几篇关于SparkStreaming的博客,那会只是作为Spark入门,快速体验Spark之用,只是照着葫芦画瓢。本文结合Spark官网上SparkStreaming的编程指南对SparkStreaming进行介绍StreamingContext如同SparkContext一样,StreamingContext也是SparkStreaming应用程序通往Spark集群的通道,它的定义…

  • DataGrid1_ItemDataBound[通俗易懂]

    DataGrid1_ItemDataBound[通俗易懂]usingSystem;usingSystem.Collections;usingSystem.ComponentModel;usingSystem.Data;usingSystem.Drawing;usingSystem.Web;usingSystem.Web.SessionState;usingSystem.Web.UI;usingSystem.Web.UI.WebContr

    2022年10月13日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号