首页 > 其他分享 >高维前缀和

高维前缀和

时间:2024-11-06 23:30:02浏览次数:1  
标签:前缀 int 如下 子集 一维 高维

高维前缀和

二维前缀和

一般的做法是容斥:

for (int i = 1; i <= n; ++ i)
    for (int j = 1; j <= n; ++ j)
        sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + a[i][j];

实际上也可以固定其他维度,依次在每一维上求前缀和,即:

for (int i = 1; i <= n; ++ i)
    for (int j = 1; j <= n; ++ j)
        a[i][j] += a[i - 1][j];
for (int i = 1; i <= n; ++ i)
    for (int j = 1; j <= n; ++ j)
        a[i][j] += a[i][j - 1];

三维前缀和

同上,有:

for (int i = 1; i <= n; ++ i)
    for (int j = 1; j <= n; ++ j)
        for (int k = 1; k <= n; ++ k) 
            a[i][j][k] += a[i - 1][j][k];
for (int i = 1; i <= n; ++ i)
    for (int j = 1; j <= n; ++ j)
        for (int k = 1; k <= n; ++ k)
            a[i][j][k] += a[i][j - 1][k];
for (int i = 1; i <= n; ++ i)
    for (int j = 1; j <= n; ++ j)
        for (int k = 1; k <= n; ++ k)
            a[i][j][k] += a[i][j][k - 1];

显然也可以拓展成 \(k\) 维。

SOSDP

要解决的是如下的问题:

对于所有的 \(i, (i \in [0, 2^n-1])\),求解 \(\sum_{j \subset i} a_j\)(或者类似于求子集某些信息)。

想法如下:

将 \(n\) 位的二进制理解为 \(n\) 维,每一维仅有两个值(0 / 1),上面说的子集其实也就是高维前缀和

故考虑枚举当前在哪一维上做前缀和,对应做即可,时间复杂度 \(\mathcal O(n 2^n)\)。

for (int j = 0; j < n; ++ j) 
    for (int i = 0; i < 1 << n; ++ i)
        if (i >> j & 1) f[i] += f[i ^ (1 << j)];

标签:前缀,int,如下,子集,一维,高维
From: https://www.cnblogs.com/chzhc-/p/18531285

相关文章

  • MySQL 字符串索引和前缀索引
    前缀索引创建前缀索引altertabletaddindexidx_email(email);altertabletaddindexidx_email(email(6));使用前缀索引,定义好长度,可以做到即节省空间,又不用额外增加太多查询成本。区分度建立索引时,区分度(不重复的值)越高越好。selectcount(distanceemail)fromt......
  • ACWING 503. 借教室 二分+前缀和
    题目描述输入格式输出格式数据范围输入样例:432543213324424输出样例:-12题目分析 每个订单都是对第s到t这个区间进行操作,所以可以用差分和前缀来实现对这段区间的快速修改。在1-m个订单中一定会有最后一个能被处理的订单,因此可将1-m分为两个区......
  • 最长公共前缀
    最长公共前缀题目链接:牛客描述给你一个大小为n的字符串数组strs,其中包含n个字符串,编写一个函数来查找字符串数组中的最长公共前缀,返回这个公共前缀。示例输入:["abca","abc","abca","abc","abcc"]返回值:"abc"思路step1:确定第i个与第i+1个字符串子串相同的公共......
  • 二维前缀和模板
    二维前缀和模板题目描述:输入一个n行m列的整数矩阵,再输入q个询问,每个询问包含四个整数x1,y1,x2,y2,表示一个子矩阵的左上角坐标和右下角坐标。对于每个询问输出子矩阵中所有数的和。输入格式:第一行包含三个整数n,m,q接下来n行,每行包含m个整数,表示整数矩阵。接下来......
  • 【算法】前缀树
    基本内容以树的方式存储字符串的数据结构,方便字符串的查找及判断是否为某一字符串的前缀入门例子PHONELST-PhoneList-洛谷|计算机科学教育新生态题目要求:判断一组字符串中是否存在某一字符串是另一字符串的前缀。例如在{“911”,“91140”,“20”,“912”}中,“911”......
  • 算法笔记:Day-04(二维前缀和)
    二维数组及滚动数组304.二维区域和检索-矩阵不可变classNumMatrix{privatefinalint[][]sum;publicNumMatrix(int[][]matrix){intm=matrix.length;intn=matrix[0].length;sum=newint[m+1][n+1];for(in......
  • 20241023 模拟赛(GCD,包含,前缀,移动)
    看题戳这里总结20min自习。上来30min先把t1写了。然后t2没看明白,先打了个暴力?然后发现值域很离谱,dfs就行了。t3t4看了一眼就跑路了。解析A.GCD难度:黄注意到只有当\(n=\)素数\(p\)的正整数次幂时,有\(f(n)=p\),其他情况都是\(f(n)=1\)。所以用欧拉筛筛一遍......
  • 每日OJ题_牛客_DP10最大子矩阵_二维前缀和_C++_Java
    目录牛客_DP10最大子矩阵_二维前缀和题目解析C++代码Java代码牛客_DP10最大子矩阵_二维前缀和最大子矩阵_牛客题霸_牛客网(nowcoder.com)描述:        已知矩阵的大小定义为矩阵中所有元素的和。给定一个矩阵,你的任务是找到最大的非空(大小至少是1*1)子矩......
  • 【算法笔记】前缀和算法原理深度剖析(超全详细版)
    【算法笔记】前缀和算法原理深度剖析(超全详细版)......
  • 矩阵前缀和
    输入一个n行m列的整数矩阵,再输入q个询问,每个询问包含四个整数x1,y1,x2,y2,表示一个子矩阵的左上角坐标和右下角坐标。对于每个询问输出子矩阵中所有数的和。#include<iostream>usingnamespacestd;intnum[1010][1010],qian[1010][1010];intmain(){intn,m,q;......