题目思路

思路:树状数组模板题

转化题意之后，问题变为:给定一个序列，需要维护两类操作:单点修改值 + 区间查询和 . 这是经典的树状数组(BIT)的应用,简称裸题/模板题。我们可以做到$O(log\ n)$ 的修改和查询。

没有接触过的同学，塔子哥在此推荐以下几个学习网站:

1.B站视频-完全理解并深入应用树状数组

推荐理由：manim制作，生动形象。UP主是鹤翔万里,OIer佬。现在浙大cs读本科。质量非常高！

2.Oi-Wiki-树状数组

推荐理由:文章质量非常高。有严谨的证明+详尽的代码+例题。此外，其他很多算法上面也有写。刷题必备。

题外话

当时这道题在赛码上是放暴力算法过了。也就是你不用上树状数组，直接模拟就能在笔试中拿满分。但是塔子哥并不推荐去赌出题人会手下留情。

类似题目推荐

leetcode

1.315. 计算右侧小于当前元素的个数

2.327. 区间和的个数

CodeFun2000

P1122 小红书-2023.03.26-第三题-涂色

P1217 华为秋招-2022年10月12日-第二题-幼儿园排队报数

P1053 华东师范大学保研机试-2022-Minimum_Sum

P1131 腾讯春招-2023.03.26-第四题-顺子区间

P1263 塔子月赛1-第二题-2333的超级队列 (树状数组上二分，难度较高!)

代码

C++

#include<bits/stdc++.h>
using namespace std;
const int N = 5e4 + 5;
// 树状数组模板
#define lb(x) ((x) & (-x))
int a[N], n, op[N], x[N], y[N];
int get_pre(int i) {
    int ret = 0;
    for (; i > 0;i -= lb(i)) ret += a[i];
    return ret;
}
void modify(int i, int val) {
    for (; i <= n; i += lb(i)) a[i] += val;
}

int get(int l, int r) {
    if (l > r) return 0;
    return get_pre(r) - get_pre(l - 1);
}
// end
int main() {
    int m;
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        cin >> op[i];
    }
    for (int i = 1; i <= m; ++i) {
        cin >> x[i];
    }
    for (int i = 1; i <= m; ++i) {
        cin >> y[i];
    }
    // 模板，没什么好讲的
    for (int i = 1; i <= m; ++i) {
        if (op[i] == 1) {
            cout << get(x[i], y[i]);
            cout << " ";
        } else {
            int p = get(x[i] , x[i]);
            modify(x[i], -p);
            modify(x[i], y[i]);
        }
    }
    return 0;
}

python

# 树状数组类
class NumArray:
    def __init__(self, nums):
        self.nums = nums
        self.tree = [0] * (len(nums) + 1)
        for i, num in enumerate(nums, 1):
            self.add(i, num)

    # 向树状数组中添加元素
    def add(self, idx, val):
        while idx < len(self.tree):
            self.tree[idx] += val
            idx += (idx & -idx)

    # 计算前缀和
    def preSum(self, idx):
        s = 0
        while idx:
            s += self.tree[idx]
            idx -= (idx & -idx)
        return s

    # 更新nums中的元素，并同步更新树状数组
    def update(self, index: int, val: int) -> None:
        self.add(index + 1, val - self.nums[index]) # 将更新差值加入树状数组中
        self.nums[index] = val # 更新nums中的元素

    # 计算区间和
    def sumRange(self, left: int, right: int) -> int:
        return self.preSum(right+1) - self.preSum(left)

n, m = map(int, input().split())
op = [[0] * m for _ in range(3)]
for i in range(3):
    op[i] = list(map(int, input().split()))

obj = NumArray([0] * n)
for i in range(m):
    if op[0][i] == 0: # 更新操作
        obj.update(op[1][i]-1, op[2][i])
    else: # 区间查询操作
        print(obj.sumRange(op[1][i]-1, op[2][i]-1), end=" ")

Java

import java.util.Scanner;

public class Main {
    static int[] tree; // 树状数组
    static int[] item; // 数组元素
    static int n; // 数组长度

    // 计算x的最后一位1所代表的数值，就是lowbit(x)
    static int lowbit(int x){
        return x & -x;
    }

    // 在树状数组的第x个位置增加u
    static void add(int x,int u){
        for (int i = x; i <= n; i+=lowbit(i)) {
            tree[i]+=u;
        }
    }

    // 查询前缀和，返回[1,x]上所有元素之和
    static int query(int x){
        int res = 0;
        for (int i = x; i >0; i-=lowbit(i)) {
            res+=tree[i];
        }
        return res;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        int m = sc.nextInt();
        int[] op = new int[m]; // 操作代码
        int[] x = new int[m]; // x参数
        int[] y = new int[m]; // y参数
        for (int i = 0; i < m; i++) {
            op[i] = sc.nextInt();
        }
        for (int i = 0; i < m; i++) {
            x[i] = sc.nextInt();
        }
        for (int i = 0; i < m; i++) {
            y[i] = sc.nextInt();
        }
        item = new int[n+1]; // 数组元素
        tree = new int[n+1]; // 树状数组
        for (int i = 1; i <= n; i++) {
            add(i,item[i]); // 初始化树状数组，将item中的元素加入其中
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < m; i++) {
            if(op[i]==0){ // 更新操作
                add(x[i],y[i]-item[x[i]]); // 将tree[x]增加y[i]-item[x[i]]，相当于更新差值
                item[x[i]] = y[i]; // 更新item[x]
            }else { // 区间查询操作
                sb.append(query(y[i])-query(x[i]-1)+ " ");
            }
        }
        System.out.println(sb.toString());
    }
}

Go

package main

import (
    "bufio"
    "fmt"
    "os"
)

var (
    n     int     // 数组长度
    tree  []int   // 树状数组
    item  []int   // 数组元素
    op    []int   // 操作代码
    x     []int   // x参数
    y     []int   // y参数
)

// 计算x的最后一位1所代表的数值，就是lowbit(x)
func lowbit(x int) int {
    return x & -x
}

// 在树状数组的第x个位置增加u
func add(x, u int) {
    for i := x; i <= n; i += lowbit(i) {
        tree[i] += u
    }
}

// 查询前缀和，返回[1,x]上所有元素之和
func query(x int) int {
    res := 0
    for i := x; i > 0; i -= lowbit(i) {
        res += tree[i]
    }
    return res
}

func main() {
    reader := bufio.NewReader(os.Stdin)
    fmt.Fscan(reader, &n)
    var m int
    fmt.Fscan(reader, &m)
    op = make([]int, m)
    x = make([]int, m)
    y = make([]int, m)
    for i := 0; i < m; i++ {
        fmt.Fscan(reader, &op[i])
    }
    for i := 0; i < m; i++ {
        fmt.Fscan(reader, &x[i])
    }
    for i := 0; i < m; i++ {
        fmt.Fscan(reader, &y[i])
    }
    item = make([]int, n+1)
    tree = make([]int, n+1)
    for i := 1; i <= n; i++ {
        add(i, item[i]) // 初始化树状数组，将item中的元素加入其中
    }

    var result string
    for i := 0; i < m; i++ {
        if op[i] == 0 { // 更新操作
            add(x[i], y[i]-item[x[i]]) // 将tree[x]增加y[i]-item[x[i]]，相当于更新差值
            item[x[i]] = y[i]           // 更新item[x]
        } else { // 区间查询操作
            result += fmt.Sprintf("%d ", query(y[i])-query(x[i]-1))
        }
    }
    fmt.Print(result)
}

Js

let input = '';
process.stdin.resume();
process.stdin.setEncoding('utf-8');
process.stdin.on('data', (data) => {
    input += data;
});
process.stdin.on('end', () => {
    const lines = input.trim().split('\n');
    const n = parseInt(lines[0].trim().split(' ')[0]);
    const m = parseInt(lines[0].trim().split(' ')[1]);

    let op = lines[1].trim().split(' ').map(Number);
    let x = lines[2].trim().split(' ').map(Number);
    let y = lines[3].trim().split(' ').map(Number);

    
    // 接下来是树状数组的模板
    let item = new Array(n+1).fill(0);
    let tree = new Array(n+1).fill(0);
    function lowbit(x){
        return x & -x;
    }
    
    function add(x,u){
        for(let i=x;i<=n;i+=lowbit(i)){
            tree[i] += u;
        }
    }
    
    function query(x){
        let res = 0;
        for(let i=x; i>0;i-=lowbit(i)){
            res += tree[i];
        }
        return res;
    }
	// end
    
    
    let sb = '';
    for(let i=0;i<m;i++){
        if(op[i]==0){ // 更新操作
            add(x[i],y[i]-item[x[i]]); // 将tree[x]增加y[i]-item[x[i]]，相当于更新差值
            item[x[i]] = y[i]; // 更新item[x]
        }else { // 区间查询操作
            sb += `${query(y[i])-query(x[i]-1)} `;
        }
    }
    console.log(sb.trim());
});

题目内容

小美是一个热爱收藏的年轻人，他喜欢收集各种有趣的物品，例如邮票、硬币、瓶盖等等。他的收藏品越来越多，于是他决定为自己在收藏架上建了一排 $n$ 个收藏夹，分别编号为 $1,2,3…n$。这样，他就可以更好地组织和展示自己的收藏品了。

小美有些时候会突发奇想改变某一个收藏美里的内容，例如从中拿入、拿出一些藏品，这些的操作会改变小美对这个收藏夹的欣赏程度，我们记编号为 $i$ 的收藏夹，小美对其的欣赏程度为 $a_i$ 。小美在休息时间经常会欣赏连续编号的收藏夹，例如编号为 $L,L+1,L+2,...,R-1,R$ 的这些收藏夹，他能从中获得的满足感为这些收藏失的欣赏程度之和，即 $\sum ^R _{i=L} a_i$ 。

小美想在欣赏之前提前估算自己能得到的满足感，想知道如果他选择编号区间为 $[L,R]$ 的收藏夹，能给他带来的满足感是多少。但是小美不想自己计算，所以他想你帮他计算一下，然后告诉他。

输入描述

第一行两个整数 $n$ 和 $m$ ，表示小美的收藏夹数量和小美的操作数量。初始时刻收藏夹都是空的，也即 $a_i = 0$ （ $i \in [1,n]$ ）

第二行 $m$ 个整数 $op_1,op_2,…,op_m$ 。

第三行 $m$ 个整数 $x_1,x_2,…,x_m$ 。

第四行 $m$ 个整数 $y_1,y_2,…,y_m$ ，这些共同表示了 $m$ 次操作，对于第 $i$ 次操作， $op_i=0$ 时表示为一次收藏夹更新操作，会将 $x_i$ 位置的收藏夹欣赏程度更新为 $y_i$ ，即 $a_{x_i} = y_i$ ； $op_i=1$ 时表示为一次查询操作，表示如果小美欣赏编号在区间 $[x_i,y_i]$ 的收藏夹，能获得的满足感是多少，也即 $\sum^{y_i}_{j=x_i} a_j$ 。

对于所有的数据， $1\le n,m \le 50000,op_i \in [0,1]$ ，当 $op_i = 0$ 时， $1\le x_i\le n,0\le y_i \le 10000$ ；当 $op_i = 1$ 时， $1\le x_i \le y_i \le n$ ，保证至少有一次 $op_i =1$ 的操作。

输出描述

对每一个 $op_i = 1$ 的操作，输出一个数表示对应答案。空格隔开所有答案。

样例

输入

4 7
1 0 1 0 1 0 1
1 1 1 3 1 4 1
3 2 3 5 3 100 3

输出

0 2 7 7

样例解释 操作记录为

0 0 0 0(初始)

询问[1,3]结果为0+0+0>

2 0 0 0<1号更改为2>

<询问[1,3],结果为2+0+0>

2 0 5 0 <3号更改为5>

<询问[1,3]结果为2+0+5>

2 0 5 100<4号更改为100>

<询问[1,3],结果为2+0+5>