以下是 LeetCode 3739. 统计主要元素子数组数目 II 的 C 语言实现。

题目分析

这道题要求统计数组 `nums` 中满足 `target` 是主要元素（出现次数严格大于子数组长度的一半）的子数组数目。

核心思路：
1. 将数组中等于 `target` 的元素视为 `1`，不等于的视为 `-1`
2. 问题转化为：统计元素和 严格大于 0 的子数组个数
3. 使用前缀和 + 树状数组（Fenwick Tree/BIT）来高效求解

关键转换：
- 设前缀和为 `s`，子数组 `[l, r]` 的和为 `s[r+1] - s[l]`
- 要求 `s[r+1] - s[l] > 0`，即 `s[r+1] > s[l]`
- 枚举右端点，用树状数组维护之前出现过的前缀和，查询小于当前前缀和的数量

C 语言实现

```c
#include <stdlib.h>
#include <string.h>

// 树状数组 (Fenwick Tree / Binary Indexed Tree)
typedef struct {
int n;
long long *c; // 使用 long long 防止溢出
} BIT;

// 初始化树状数组
BIT* bitCreate(int n) {
BIT *bit = (BIT*)malloc(sizeof(BIT));
bit->n = n;
bit->c = (long long*)calloc(n + 1, sizeof(long long));
return bit;
}

// 释放树状数组
void bitFree(BIT *bit) {
free(bit->c);
free(bit);
}

// 单点更新：在位置 x 增加 delta
void bitUpdate(BIT *bit, int x, long long delta) {
while (x <= bit->n) {
bit->c[x] += delta;
x += x & -x; // 加上 lowbit
}
}

// 前缀查询：查询 [1, x] 的和
long long bitQuery(BIT *bit, int x) {
long long res = 0;
while (x > 0) {
res += bit->c[x];
x -= x & -x; // 减去 lowbit
}
return res;
}

/**
* 统计主要元素子数组数目 II
* @param nums 整数数组
* @param numsSize 数组长度
* @param target 目标元素
* @return 满足条件的子数组数目
*/
long long countMajoritySubarrays(int* nums, int numsSize, int target) {
// 前缀和范围: [-n, n]，整体右移 n+1 个单位变为 [1, 2n+1]
int offset = numsSize + 1; // 偏移量
int size = 2 * numsSize + 1; // 树状数组大小

BIT *bit = bitCreate(size);

// 初始前缀和为 0，对应位置 offset，计数为 1
bitUpdate(bit, offset, 1);

long long ans = 0;
int s = offset; // 当前前缀和（已偏移）

for (int i = 0; i < numsSize; i++) {
// 等于 target 则 +1，否则 -1
s += (nums[i] == target) ? 1 : -1;

// 查询前缀和小于当前 s 的数量（即查询 [1, s-1] 的和）
ans += bitQuery(bit, s - 1);

// 将当前前缀和加入树状数组
bitUpdate(bit, s, 1);
}

bitFree(bit);
return ans;
}
```

复杂度分析

指标 复杂度
时间复杂度 O(n log n)，每个元素进行两次树状数组操作，每次 O(log n)
空间复杂度 O(n)，树状数组需要 2n+1 的空间

思路详解

1. 问题转换：设子数组中 `target` 出现 `cnt` 次，长度为 `len`。条件 `cnt > len/2` 等价于 `2*cnt > len`。令 `target` 为 `1`，其他为 `-1`，则子数组和 `> 0` 即满足条件。

2. 前缀和：设前缀和数组 `pre[i]` 表示前 `i` 个元素的和。子数组 `[l, r]` 的和为 `pre[r+1] - pre[l]`。

3. 树状数组维护：枚举右端点 `r`，需要找满足 `pre[l] < pre[r+1]` 的左端点 `l` 的数量。用树状数组维护之前所有前缀和的出现次数，支持：
- `query(x)`：查询小于等于 `x` 的前缀和个数
- `update(x, 1)`：将当前前缀和加入

4. 偏移处理：前缀和范围是 `[-n, n]`，树状数组下标从 1 开始，所以整体偏移 `n+1`。