【算法】-前缀和之前缀和的前缀和
2022/5/24 1:21:33
本文主要是介绍【算法】-前缀和之前缀和的前缀和,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
思想
计算前缀和
python计算前缀和有两种方法,一种是直接计算,一种是调用库函数
# 方法1:计算前缀和 n = len(a) s = [0] * (n+1) # 第一个存储的0,s[i] = a0+...ai-1 for i, v in enumerate(a): s[i+1] = s[i]+v for i, v in enumerate(s): ss[i+1] = s[i] + v # 方法2:调用库函数 s = accumulate(a, initial=0) # 计算前缀和的和 ss = list(accumulate(s,initial=0))
使用c++进行计算前缀和
int n = a.size() vector<int> pre_sum(n+1,0),pre_pre_sum(n+1,0); rep(i,0,n)pre[i+1] = pre[i] + a[i]; rep(i,0,n)pre_pre_sum = pre_pre_sum[i] + pre[i];
模板 #include<bits/stdc++.h> #define D(...) fprintf(stderr,__VA_ARGS__) #define DD(...) D(#__VA_ARGS__ "="),debug_helper::debug(__VA_ARGS__),D("\n") #include"/home/xay5421/debug.hpp" #else #define D(...) ((void)0) #define DD(...) ((void)0) #endif #define pb push_back #define eb emplace_back #define SZ(x) ((int)(x).size()) #define each(x,v) for(auto&x:v) #define rep(i,a,b) for(int i=(a);i<=(b);++i) #define per(i,a,b) for(int i=(a);i>=(b);--i) using namespace std; using LL=long long; using ULL=unsigned long long; const int P=1e9+7; int ad(int k1,int k2){return k1+=k2-P,k1+=k1>>31&P;} int su(int k1,int k2){return k1-=k2,k1+=k1>>31&P;} int mu(int k1,int k2){return 1LL*k1*k2%P;} void uad(int&k1,int k2){k1+=k2-P,k1+=k1>>31&P;} void usu(int&k1,int k2){k1-=k2,k1+=k1>>31&P;} template<class... T>int ad(int k1,T... k2){return ad(k1,ad(k2...));} template<class... T>int su(int k1,T... k2){return su(k1,ad(k2...));} template<class... T>int mu(int k1,T... k2){return mu(k1,mu(k2...));} template<class... T>void uad(int&k1,T... k2){return uad(k1,ad(k2...));} template<class... T>void usu(int&k1,T... k2){return usu(k1,ad(k2...));} int po(int k1,int k2){ int k3=1; for(;k2;k2>>=1,k1=mu(k1,k1))if(k2&1)k3=mu(k3,k1); return k3; } const int N=100005; int n; int a[N],st[N],top,lc[N],rc[N]; int s1[N],s2[N],s3[N]; int ans; int calc1(int l,int r){ return su(s1[r],s1[l-1],mu(l-1,su(s3[r],s3[l-1]))); } int calc2(int l,int r){ return ad(su(s2[r],s2[l-1]),mu(r+1,su(s3[r],s3[l-1]))); } void dfs(int u,int l,int r){ if(l>r)return; uad(ans,mu(a[u],ad(mu(calc1(l,u),r-u+1),mu(calc2(u+1,r),u-l+1)))); dfs(lc[u],l,u-1); dfs(rc[u],u+1,r); }
这篇关于【算法】-前缀和之前缀和的前缀和的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?
- 2024-05-09企业src漏洞挖掘-有意思的命令执行