树状数组+差分

$O(nlogn)$

注意对输入的处理

C++ 代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 1e5 + 5;

int a[N],t[N];
int n,m;

int lowbit(int x){
    return x & -x;
}

void add(int x,int k){
    for(int i = x;i<=n;i+=lowbit(i)){
        t[i] += k;
    }
}

int ask(int x){
    int res = 0;
    for(int i = x;i;i-=lowbit(i)){
        res += t[i];
    }
    return res;
}

int main() {
    scanf("%d%d",&n,&m);

    int x,l,r,d;
    for(int i = 1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    char op[2];
    while(m--){
        scanf("%s",op);
        if(op[0]=='C'){
            scanf("%d%d%d",&l,&r,&d);
            add(l,d);
            add(r+1,-d);
        }
        else{
            scanf("%d",&x);
            printf("%d\n",ask(x)+a[x]);
        }
    }
    return 0;
}

Python 代码

def lowbit(x):
    return x & -x

def add(x, k):
    while x <= n:
        t[x] += k
        x += lowbit(x)

def ask(x):
    res = 0
    while x > 0:
        res += t[x]
        x -= lowbit(x)
    return res

n, m = map(int, input().split())

a = [0] + list(map(int, input().split()))

t = [0] * (n + 10)

for _ in range(m):
    str = input().split()
    if str[0] == "C":
        l, r, d = map(int, str[1:])
        add(l, d)
        add(r+1, -d)
    else:
        x = int(str[1])
        print(a[x] + ask(x))