2025-01-19：数组中的峰值用go语言，在一个整数数组 nums 中，若

摘要：• 一个元素 nums[i] 被认为是峰值元素，当且仅当 nums[i] 大于相邻的两个元素 nums[i-1] 和 nums[i+1]，即 nums[i] > nums[i-1] 且 nums[i] > nums[i+1]。

2025-01-19：数组中的峰值。用go语言，在一个整数数组 nums 中，若某个元素大于其左右相邻的元素，则称该元素为“峰值”元素。

你会得到一个整数数组 nums 和一个二维数组 queries。需要处理两种操作：

1.queries[i] = [1, li, ri]：计算子数组 nums[li..ri] 中的峰值元素数量。

2.queries[i] = [2, indexi, vali]：将 nums[indexi] 的值更改为 vali。

最终，你需要返回一个数组 answer，其中依次包含了每一次第一种操作的结果。

请注意，子数组的第一个和最后一个元素不被视为峰值元素。

queries[i][0] == 1 或者 queries[i][0] == 2。

对于所有的 i ，都有：

queries[i][0] == 1 ：0

queries[i][0] == 2 ：0

输入：nums = [4,1,4,2,1,5], queries = [[2,2,4],[1,0,2],[1,0,4]]。

输出：[0,1]。

解释：

第一个操作：nums[2] 变为 4 ，它已经是 4 了，所以保持不变。

第二个操作：[4,1,4] 中峰值元素的数目为 0 。

第三个操作：第二个 4 是 [4,1,4,2,1] 中的峰值元素。

答案2025-01-19：

chatgpt[1]

题目来自leetcode3187。

1.定义峰值：

• 一个元素 nums[i] 被认为是峰值元素，当且仅当 nums[i] 大于相邻的两个元素 nums[i-1] 和 nums[i+1]，即 nums[i] > nums[i-1] 且 nums[i] > nums[i+1]。

2.初始化 Fenwick Tree：

• 创建一个 Fenwick Tree (称为 f)，其大小为 n-1，用于存储可能的峰值数量。• 在树的初始化阶段，遍历 nums 数组，检查 nums[i] 是否为峰值，若是，则在 Fenwick Tree 中更新相应的值。

3.查询操作：

• 当处理 queries[i] = [1, li, ri] 的查询时，使用 Fenwick Tree 的 query 方法计算 li 到 ri 的子数组中峰值的数量。• 注意，只有子数组的 li 和 ri 之间的元素（不包括边界元素）将被视为可能的峰值。

4.更新操作：

• 当处理 queries[i] = [2, index, value] 的更新操作时，需要将 nums[index] 更新为 value。• 在更新之前，需要检查 index 左边的 index-1 和右边的 index+1 元素是否会影响已有的峰值。如果 nums[index-1] 和 nums[index+1] 与 nums[index] 的新值不再符合峰值的条件，则在 Fenwick Tree 中对应减去峰值数量。• 执行更新后，再次检查更新后的 nums[index-1] 和 nums[index+1]，如果新的值符合峰值条件，则在 Fenwick Tree 中对应增加峰值数量。

5.返回结果：

• 所有查询类型为 1 的结果将被存储在列表中，最后返回该列表作为输出。• 初始化阶段：遍历 nums 的长度为 n，每次更新 Fenwick Tree 最多需 O(log n) 的时间。初始化的时间复杂度为 O(n log n)。• 每个查询操作（类型 1）：也是 O(log n)，因此如果有 q 个此类请求，总的时间复杂度是 O(q log n)。• 更新操作（类型 2）同样是 O(log n)，因此如果有 q 个此类请求，总的时间复杂度也是 O(q log n)。

综上所述，综合处理所有的操作，总的时间复杂度为：O(n log n)+O(q log n)。

• 使用了一个 Fenwick Tree 数组，大小为 n-1，因此额外空间复杂度为 O(n)。• 由于我们只用了少量额外的变量，整体的空间复杂度依旧为 O(n)。package mainimport ("fmt")type fenwick intfunc (f fenwick) update(i, val int) {for ; i 0; i &= i - 1 {res += f[i]}return res}func (f fenwick) query(l, r int) int {if r nums[i+1] {f.update(i, val)}}for i := 1; i

在这里插入图片描述

struct Fenwick {tree: Vec,}impl Fenwick {fn new(size: usize) -> Self {Fenwick {tree: vec![0; size + 1],}}fn update(&mut self, index: usize, value: i32) {let mut i = index as isize;while i i32 {let mut res = 0;let mut i = index as isize;while i > 0 {res += self.tree[i as usize];i &= i - 1;}res}fn query(&self, left: usize, right: usize) -> i32 {if right , queries: Vec>) -> Vec {let n = nums.len;let mut f = Fenwick::new(n - 1);fn update_peak(f: &mut Fenwick, nums: &[i32], i: usize, val: i32) {if i > 0 && i nums[i + 1] {f.update(i, val);}}}for i in 1..(n - 1) {update_peak(&mut f, nums, i, 1);}let mut ans = Vec::new;for q in queries {if q[0] == 1 {ans.push(f.query((q[1] + 1) as usize, (q[2] - 1) as usize));} else {let i = q[1] as usize;for j in max(i as isize - 1, 1) as usize..=min(i + 1, n - 2) {update_peak(&mut f, nums, j, -1);}nums[i] = q[2];for j in max(i as isize - 1, 1) as usize..=min(i + 1, n - 2) {update_peak(&mut f, nums, j, 1);}}}ans}fn main {let mut nums = vec![4, 1, 4, 2, 1, 5];let queries = vec![vec![2, 2, 4], vec![1, 0, 2], vec![1, 0, 4]];let result = count_of_peaks(&mut nums, queries);println!("{:?}", result);}// 輔助函數fn max(a: isize, b: isize) -> isize {if a > b {a} else {b}}fn min(a: usize, b: usize) -> usize {if a

在这里插入图片描述

C完整代码如下：#include #include typedef struct {int *tree;int size;} Fenwick;void fenwick_init(Fenwick *f, int size) {f->size = size + 1; // 使用1-based索引f->tree = (int *)calloc(f->size, sizeof(int));}void fenwick_update(Fenwick *f, int index, int value) {for (; index size; index += index & -index) {f->tree[index] += value;}}int fenwick_pre(Fenwick *f, int index) {int sum = 0;for (; index > 0; index &= index - 1) {sum += f->tree[index];}return sum;}int fenwick_query(Fenwick *f, int left, int right) {if (right nums[i + 1]);}void update_peak(Fenwick *f, int *nums, int i, int val) {if (i > 0 && i size - 1)) {if (is_peak(nums, i)) {fenwick_update(f, i, val);}}}void count_of_peaks(int *nums, int n, int queries[3], int query_count, int *result, int *result_count) {Fenwick f;fenwick_init(&f, n - 1);for (int i = 1; i 1 ? i - 1 : 1); j 1 ? i - 1 : 1); j

在这里插入图片描述

#include #include #include using namespace std;class Fenwick {public:vector tree;Fenwick(int size) {tree.resize(size + 1, 0); // 1-based index}void update(int index, int value) {for (; index 0; index &= index - 1) {sum += tree[index];}return sum;}int query(int left, int right) {if (right &nums, int i, int val) {if (i > 0 && i nums[i + 1]) {f.update(i, val);}}}vector count_of_peaks(vector &nums, vector> &queries) {int n = nums.size;Fenwick f(n - 1);for (int i = 1; i ans;for (const auto &q : queries) {if (q[0] == 1) {ans.push_back(f.query(q[1] + 1, q[2] - 1));} else {int i = q[1];for (int j = max(i - 1, 1); j nums = {4, 1, 4, 2, 1, 5};vector> queries = {{2, 2, 4}, {1, 0, 2}, {1, 0, 4}};vector result = count_of_peaks(nums, queries);for (int res : result) {cout

在这里插入图片描述

# -*-coding:utf-8-*-class FenwickTree:def __init__(self, size):self.size = sizeself.tree = [0] * (size + 1) # 1-based indexdef update(self, index, value):while index 0:total += self.tree[index]index -= index & -indexreturn totaldef query(self, left, right):if right nums[i + 1]def update_peak(fenwick_tree, nums, i, value):if 1

在这里插入图片描述

class FenwickTree {constructor(size) {this.size = size;this.tree = new Array(size + 1).fill(0); // 使用1-based索引}update(index, value) {for (let i = index; i 0; i &= (i - 1)) {sum += this.tree[i];}return sum;}query(left, right) {if (right nums[i + 1];}function updatePeak(fenwick, nums, i, value) {if (i > 0 && i