首页 > 其他分享 >n阶前缀和 の 拆解

n阶前缀和 の 拆解

时间:2024-07-06 17:31:03浏览次数:16  
标签:他加 前缀 cdot sum Large 拆解

2阶

\[\sum_{i=l}^{r} \sum^{i}_{j=1} a_j \]

\[=\sum_{i=l}^{r} (r-i+1) a_i \]

\[=(r+1)\sum_{i=l}^{r} a_i+\sum_{i=l}^{r} i \cdot a_i \]

这个很好理解,因为对于第 \(i\) 个数,他加了 \((r-i+1)\) 次

三阶

正常拆解

\[\sum_{i=l}^{r} \sum^{i}_{j=1} \sum_{k}^{j} a_k \]

\[=\sum_{i=l}^{r} \sum_{j=1}^{i} (i-j+1) a_j \]

\[=\sum_{i=l}^{r} {\Large (}i \cdot \sum_{j=1}^{i} a_j + \sum_{j=1}^{i} a_j - \sum_{j=1}^{i} j \cdot a_j{\Large )} \]

\[=\sum_{i=l}^{r} i \cdot \sum_{j=1}^{i} a_j + \sum_{i=l}^{r} \sum_{j=1}^{i} a_j - \sum_{i=l}^{r} \sum_{j=1}^{i} j \cdot a_j \]

注意到 \(\sum_{i=l}^{r} \sum_{j=1}^{i} a_j\) 看起来很眼熟,其余的 \(\sum\) 不过多乘了一个 \(i\) 或 \(j\) ,可得:

\[\sum_{i=l}^{r} i \cdot \sum_{j=1}^{i} a_j + \sum_{i=l}^{r} (r-i+1) a_j - \sum_{i=l}^{r} (r-i+1)() \cdot a_i \]

标签:他加,前缀,cdot,sum,Large,拆解
From: https://www.cnblogs.com/whrwlx/p/18287504

相关文章

  • 前缀和数组 差分数组
    前缀和一维:通过空间换时间适用于需要频繁查询某一段区间和的场景。一维数组:一维前缀和中的每一项:,该前缀和中的每一项也就是数组中对应的前i项和。一维前缀和数组的构造:在输入原数组时同步构造前缀和数组可以改写为  for(inti=1;i<=n;i++){scanf("%d",&arr[i......
  • Stable Diffusion做AI儿童绘本副业创收居然超主业?变现方式详细拆解!新手小白必看!
    AI儿童绘本各大平台上故事绘本、幼儿园儿歌、英文绘本、古诗词,从下图里,可以看出需求量很大AI儿童绘本实现方式\1.gpt\2.leonardo.ai\3.Midjourney\4.StableDiffusion变现方式\1.自制绘本售卖\2.卖书卖课针对各位初学者,这里列举了一条完整的学习计划,感兴趣的可......
  • Stable Diffusion利用AI绘画打造治愈系小黑猫壁纸账号,玩法拆解!
    前言大家好,这篇文章给大家分享一个某书风口项目玩法。起初发布的卡通形象效果平平,但转向治愈系小黑猫后,流量迅速增长,许多内容获得了上千个赞。某书平台上有大量爱猫用户,因此猫咪相关的内容很容易火爆。利用AI绘画制作猫咪相关作品,再结合职场人和打工人的文案,能给用户一......
  • [算法篇] 简单讲讲一维前缀和与差分
    前缀和:先给定义:指某序列的前n项和是不是与我们高中所学的数列求和类似?给出用途: 如我们于一组长度为n的整数序列中询问m次,每次询问中输出区间[l,r]中数之和倘若我们先不使用前缀和,预测一下思路将会是:m次询问中,每一次都求和数组[l,r]时间复杂度为O(n),思路很简单但若m非常大则将......
  • AI 大模型应用开发实战(04)-AI生态产业拆解
    1行业全景图2结构拆解AIGC生成式AI这个产业。分成上中下游三大块。2.1上游基础层主要包括:算力:包括AI芯片和云服务等,例如像英伟达、AMD以及华为等厂商提供的算力基础设施。大型模型基于Transformer架构,对算力的需求很大。数据:新时代的石油,分为基础数据服务、数据集和向......
  • 前缀和
    前缀和前缀和是什么可以说,前缀和是一种优化程序运行时间的一种方法,一般用于求一个序列中的区间和。前缀和的原理顾名思义,前缀和数组,即一个序列中前\(i\)个数据之和。\[b_i=\sum_{j=0}^{i}a_j\]所以\(a_l\)到\(a_r\)的和是:\[\sum_{j=l}^{r}a_j=b_r-b_{l-......
  • 怪物猎人世界:冰原拆解
    《怪物猎人世界:冰原》系统拆解分析此次是第一次练习从多方面写游戏的系统拆解目的是为了验证总结自己学习游戏策划方面的知识,以及以后回顾自己的学习。目录游戏概述核心机制游戏设计游戏系统总结1.游戏概述游戏名称:怪物猎人世界:冰原开发商和发行商:CAPCOM平台:PS4,PS5......
  • DevOps学习回顾02-实践的通用路径-需求分析的拆解-CI的理解-质量体系的实践路径
    参考来源:极客时间专栏:DevOps实战笔记,作者:石雪峰课程链接:https://time.geekbang.org/column/intro/235DevOps学习回顾02-实践的通用路径-需求分析的拆解-CI的理解-质量体系的实践路径DevOps实践的通用路径第一步:寻找合适的试点项目一个合适的项目应该具备以下几个特......
  • 震惊:全面拆解dapp上线三天、 规则漏洞导致资金全部损失
    背景:今天的分析的是链上一个土狗项目由于规则设计漏洞、导致被黑客利用漏洞攻击、致使资金全部损失的案例、近期这个项目也是圈内很火、今天看到了,就趁周末有时间从技术的角度,分析黑客如何利用链上部署的合约,进而干废项目方。今天说的这个,不是技术漏洞bug、是规则设计漏洞......
  • 【数据结构】前缀树(字典树)汇总
    基础{“a”,“abc”,“bac”,“bbc”,“ca”}的字典树如下图:最主用的应用:一,字符串编码。二,位运算。字符串编码相比利用哈希映射编码,优点如下:依次查询长度为n的字符串s的前缀时间复杂度是O(n)。查询完s[0…i],再查询s[0…i+1]的时间复杂度是O(1)。而哈希映射的时间复杂......