摘要
Title: 1264. 动态求连续区间和
Tag: 树状数组、线段树
Memory Limit: 64 MB
Time Limit: 1000 ms

1264. 动态求连续区间和

题意

给定 n 个数组成的一个数列，规定有两种操作，一是修改某个元素，二是求子数列 [a,b] 的连续和。
思路

树状数组：

ps:
- 定义： $tr[x] = (a[x - lowbit[x]], a[x]]$ $t r [x] = (a [x - l o w b i t [x]], a [x]]$
  - lowbit(x) 代表x二进制下最后一个1，或者 $2^k$ （k代表x二级制下x后面有多少个连续的0）
- 树状数组的每一条边，若当前节点是 $x$ 的话，父节点就是 $x+lowbit(x)$
- add操作只能实现一个位置加上一个数，若想实现变成一个数，可以加上它们的差
- 树状数组只能实现 单点修改和区间查询，其余类似于区间修改，是在结合差分思想后衍生出的做法
线段树：

代码

树状数组

'''
Author: NEFU AB-IN
Date: 2022-03-26 16:06:33
FilePath: \ACM\Acwing\1264.py
LastEditTime: 2022-03-26 16:06:35
'''
N = int(1e5 + 10)
tr, a = [0] * N, [0] * N

def lowbit(x):
    return x & -x
def add(x, d):
    while x < N:
        tr[x] += d
        x += lowbit(x)
def query(x):
    ans = 0
    while x:
        ans += tr[x]
        x -= lowbit(x)
    return ans

n, m = map(int, input().split())
a[1:] = list(map(int, input().split()))

for i in range(1, n + 1): #一定下标从1开始
    add(i, a[i])
for i in range(m):
    k, x, y = map(int, input().split())
    if k: add(x, y)
    else: print(query(y) - query(x - 1))

线段树 TLE, 高效的写法，可能是要将Node中的元素拿出来，用array存

'''
Author: NEFU AB-IN
Date: 2022-03-26 17:50:51
FilePath: \ACM\Acwing\1264.1.py
LastEditTime: 2022-03-26 20:08:04
'''
from array import array


class Node():
    def __init__(self, l, r):
        self.l = l
        self.r = r
        self.sum = 0


N = int(1e5 + 10)
tr = [Node(0, 0) for _ in range(N << 2)]
a = [0] * N


def pushup(p):
    tr[p].sum = tr[p << 1].sum + tr[p << 1 | 1].sum


def build(p, l, r):
    tr[p] = Node(l, r)
    if l == r:
        tr[p].sum = a[l]
        return
    mid = l + r >> 1
    build(p << 1, l, mid)
    build(p << 1 | 1, mid + 1, r)
    pushup(p)


def modify(p, k, v):
    if k <= tr[p].l and tr[p].r <= k:
        tr[p].sum += v
        return
    mid = tr[p].l + tr[p].r >> 1
    if k <= mid: modify(p << 1, k, v)
    if k > mid: modify(p << 1 | 1, k, v)
    pushup(p)


def query(p, l, r):
    sum = 0
    if l <= tr[p].l and tr[p].r <= r:
        return tr[p].sum
    mid = tr[p].l + tr[p].r >> 1
    if l <= mid: sum += query(p << 1, l, r)
    if r > mid: sum += query(p << 1 | 1, l, r)
    return sum


n, m = map(int, input().split())
a[1:] = list(map(int, input().split()))
build(1, 1, n)
for i in range(m):
    k, x, y = map(int, input().split())
    if k:
        modify(1, x, y)
    else:
        print(query(1, x, y))

1264. 动态求连续区间和

题意

思路

代码