题意

给出长度为1e5的数组和1e5次操作，每次操作可能为单点修改，也可能为区间查询

思路

数据范围是1e5，考虑用数据结构维护，树状数组或线段树都可以

树状数组是一种支持单点修改和区间查询的代码量小的数据结构，维护的信息和运算必须要满足结合律而且可差分，比如加法、乘法、异或等。

• 结合律：(x # y )# z = x # (y # z)，其中#为二元运算符，比如+ * ^
• 可差分：具有逆运算的运算，即已知 x # y 和 x 可以求出y

需要注意的是：

• mod 意义下的乘法如果要差分，需要保证每个数都存在逆元（模数为质数时一定存在逆元）
• gcd、max这些信息不可差分

树状数组解决的是线段树解决的问题的子集，但是树状数组代码量少，常数小。

基本原理就是把前缀[1,n]拆成不多于logn段区间，使得这logn段区间的信息是已知的，那么合并的时候只需要合并logn段区间的信息就可以得到答案，以前需要合并n个信息

具体可以看 oiwiki

Go代码

package main

import (
    "fmt"
)

const maxn = 1e5 + 7 
var tree = make([]int,maxn) 
var n int 

func lowbit(x int) int {
    return x & -x 
}
func add(idx,x int) {
    for idx <= n {
        tree[idx] += x 
        idx += lowbit(idx)
    }
}

func query(idx int) int {
    ans := 0 
    for idx > 0 {
        ans += tree[idx]
        idx -= lowbit(idx)
    }
    return ans 
}

func main() {
    var q,op,l,r int 
    fmt.Scan(&n,&q)
    a := make([]int,n+1)
    for i := 1; i <= n; i ++ {
        fmt.Scan(&a[i])
        add(i,a[i]) //记得要建树
    }
    for ; q > 0; q -- {
        fmt.Scan(&op,&l,&r)
        if op == 1 {
            add(l,r)
        }else{
            fmt.Println(query(r) - query(l-1))
        }
    }
    
}