Segmented Exclusive Prefix Sum

原始题目：LeetGPU - Segmented Exclusive Prefix Sum

题目描述

给定 $N$ 个 32 位浮点数的数组 values 和等长的整数数组 flags，其中 flags[i] = 1 表示新段的开始，flags[i] = 0 表示继续当前段。计算每段内的互斥前缀和（exclusive prefix sum）并存储在 output 中。

第一个元素始终是段起始（$flags[0] = 1$）。在每段内，$output[i]$ 等于该段中出现在索引 $i$ 之前的所有值的和，因此每段的第一个元素始终为 $0.0$。

实现要求

• 不允许使用外部库。
• solve 函数签名必须保持不变。
• 最终结果必须存储在 output 中。
• 从 values 和 flags 读取，向 output 写入。

示例

Input:  values = [1.0, 2.0, 3.0, 4.0, 5.0, 6.0]
        flags  = [  1,   0,   0,   1,   0,   1]

Segments: [1,2,3] | [4,5] | [6]

Output:  [0.0, 1.0, 3.0, 0.0, 4.0, 0.0]
         (段1: [1,2,3]的互斥前缀和 → [0,1,3])
         (段2: [4,5]  的互斥前缀和 → [0,4])
         (段3: [6]    的互斥前缀和 → [0])

约束条件

• $1 \le N \le 100{,}000{,}000$
• $flags[0] = 1$，$flags[i] \in \{0, 1\}$
• 值为 32 位浮点数，范围 $[-100, 100]$
• 性能测试在 $N = 50{,}000{,}000$ 的规模下进行。

解题思路

分段前缀和 = 段边界重置 + 段内标准前缀和。核心挑战在于段边界打破了前缀和的连续性。关键技巧是检测 flags[i] = 1 时重置累加器为零。在线程协作层面，需要将输入分段后每个 block 先做内部 scan（包含段边界逻辑），再跨 block 传递段信息。欢迎在 GitHub Discussions 分享你的解法。