← 返回编程题库
coding-sector-day-return-rect-queries中等免费版2000ms未尝试

行业-交易日 收益方块:矩形区间求和的批量查询

Sector-Day Return Cube: Batched Rectangular Range Sums

开始编码

实现 solution(returns_matrix: list[list[float]], queries: list[list[int]]) -> list[float]。给定一个日度收益方块 returns_matrix[D][S](D 个交易日为行,S 个行业为列;每格为该行业当天的带符号十进制收益,例如 0.0123 表示 +1.23%),以及 Q 条矩形查询 queries,每条查询为四元组 [d_lo, d_hi, s_lo, s_hi],上下界均为闭区间(0 <= d_lo <= d_hi < D0 <= s_lo <= s_hi < S)。返回长度为 Q 的浮点列表,第 k 个元素为第 k 条查询所对应矩形子块 returns_matrix[d_lo..d_hi][s_lo..s_hi] 内所有收益之和

例:若 returns_matrix = [[0.01, -0.02, 0.005, 0.0], [0.012, 0.003, -0.01, 0.004], [-0.005, 0.0, 0.008, 0.002]]queries = [[0,1,0,1], [0,2,0,3]],第一条查询覆盖第 0..1 行、第 0..1 列,求和为 0.01 + (-0.02) + 0.012 + 0.003 = 0.005;第二条查询覆盖整个方块,求和为 0.009

查询为空 (Q == 0) 时返回 []。空矩阵情形(D == 0S == 0)只有在 Q == 0 时才是良定义的——按规范,对空方块发起查询的责任在调用方。

朴素逐查询双重循环每条 O(D*S),整体 O(Q*D*S) = 2*10^8 量级,会在隐藏大样本上超时;正解一次性构建 (D+1) x (S+1) 的二维前缀和索引,每条查询通过容斥在 O(1) 内回答。

实现细节由 stubs/stub.py 提供。

实践背景

多策略交易台收盘后会得到一个行业 × 交易日的收益方块,紧接着 PM 与风控会抛来大量临时性的矩形切片问题——"过去财报周科技板块的累计收益"、"三季度全部行业的合计"、"近五个交易日能源加材料"。会话循环里在方块加载时一次性构建二维前缀和索引(D*S <= 40000,开销可忽略),之后每个矩形聚合就是四次查表,便宜到分析师可以交互式地连发几千条切片问题,而不需要重跑内部求和。把索引预先建好与逐次惰性求和之间的差距,正是亚秒级切片与肉眼可感知卡顿之间的距离;同一招在交易台后续把视角拓到三维方块(日期 × 行业 × 因子)时也能直接复用。

约束条件

  • 0 <= D <= 200 且 0 <= S <= 200,其中 D = len(returns_matrix);当 D > 0 时 S = len(returns_matrix[0])
  • 0 <= Q <= 5000,其中 Q = len(queries)
  • 每条查询为 [d_lo, d_hi, s_lo, s_hi],满足 0 <= d_lo <= d_hi < D 且 0 <= s_lo <= s_hi < S;上下界均为闭区间
  • 每个 returns_matrix[i][j] 是带符号浮点数,绝对值不超过 1.0(十进制收益,例如 0.0123 表示 +1.23%)
  • 输出为长度 Q 的浮点列表,按绝对误差 1e-9 比对;当 Q == 0 时返回 []

样例

Case 1 · statement-example: 3x4 matrix two queries

输入: [[[0.01,-0.02,0.005,0],[0.012,0.003,-0.01,0.004],[-0.005,0,0.008,0.002]],[[0,1,0,1],[0,2,0,3]]]

期望: [0.004999999999999999,0.009]

查询0=行0..1列0..1之和=0.01-0.02+0.012+0.003=0.005;查询1=整张表之和。

Case 2 · visible: single-cell query

输入: [[[0.05,-0.03],[0.02,0.01]],[[0,0,0,0],[1,1,1,1]]]

期望: [0.05,0.009999999999999995]

两次单格查询分别返回 m[0][0]=0.05 与 m[1][1]=0.01。

Case 3 · visible: empty queries returns empty list

输入: [[[0.01,0.02],[0.03,0.04]],[]]

期望: []

查询列表为空时返回空列表。

最近提交

还没有提交记录。

编码区

实现 solution(...)。本地运行当前支持 Python 可见样例;服务端提交会运行可见样例和隐藏测试。

加载编辑器...
计时0:00

默认展示公开样例。点击「运行样例」后会在这里显示实际输出;点击「提交评测」会进入隐藏测试。

Case 1 · statement-example: 3x4 matrix two queries

输入: [[[0.01,-0.02,0.005,0],[0.012,0.003,-0.01,0.004],[-0.005,0,0.008,0.002]],[[0,1,0,1],[0,2,0,3]]]

期望: [0.004999999999999999,0.009]

查询0=行0..1列0..1之和=0.01-0.02+0.012+0.003=0.005;查询1=整张表之和。

Case 2 · visible: single-cell query

输入: [[[0.05,-0.03],[0.02,0.01]],[[0,0,0,0],[1,1,1,1]]]

期望: [0.05,0.009999999999999995]

两次单格查询分别返回 m[0][0]=0.05 与 m[1][1]=0.01。

Case 3 · visible: empty queries returns empty list

输入: [[[0.01,0.02],[0.03,0.04]],[]]

期望: []

查询列表为空时返回空列表。