3389. 线段树:点增加

10185101162

重要的事情说三遍!
开long long!
开long long!
开long long!

qqqqqcy

基本操作确实树状数组比线段树快。
比递归版的快2倍。
非递归的感觉已经速度差不多了。

#include <bits/stdc++.h>
using namespace std;    
typedef long long long_int;
const int maxn = 550000;
long_int Tree[maxn];
int n , m;
inline int lowbit(int x){ return x&(-x); }
void add(int x, long_int val){
    for (int i = x ; i <= n ; i += lowbit(i))
        Tree[i] += val; 
}
long_int get(int x){
    long_int sum = 0;
    for (int i = x ; i ; i -= lowbit(i))
        sum += Tree[i];
    return sum;
}

int main(){
    cin >> n;
    long_int x = 0;
    for (int i = 1 ; i <= n ; ++i){
        scanf("%lld",&x);
        add(i,x);
    }
    cin >> m;
    int a = 0 , y = 0 , z = 0;
    while(m--){
        scanf("%d%d%d",&a,&y,&z);
        if(a == 1)
            add(y,z);
        else
            printf("%lld\n",get(z) - get(y-1));
    }
    return 0;
}
10175101282

推荐一种写法:zkw线段树.(详见统计的力量)

(相比线段树:)
优点:代码量较少,空间需求略少(实际上不需要4倍),运行效率较高(非递归);
缺点:应用范围有限制.尽管可以稍加修改就支持单点更新/单点查询/区间更新/区间求和/区间RMQ等,但其中部分功能似乎不能同时实现…

总体来说,无论是代码量还是应用范围都介于树状数组和递归版线段树之间.

关于这个数据结构还在摸索…

栗子:

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

#define pushup(x) T[x]=T[x<<1]+T[x<<1|1]
const int maxn = 500005;
int n, m, M;
long long T[maxn<<4];

inline void build()
{
    for (M = 1; M <= n+1; M <<= 1);
    for (int i = M+1; i <= M+n; ++i) scanf("%lld", T+i);
    for (int i = M-1; i; --i) pushup(i);
}

inline void update(int x, int y)
{
    for (T[x+=M] += y, x>>=1; x; x>>=1) pushup(x);
}

inline void query(int s, int t)
{
    long long ans = 0;
    for (s += M-1, t += M+1; s^t^1; s>>=1, t>>=1)
    {
        if (~s&1) ans += T[s^1];
        if (t&1) ans += T[t^1];
    }
    printf("%lld\n", ans);
}

int main()
{
    int op, x, y;
    scanf("%d", &n);
    build();
    scanf("%d", &m);
    while (m--)
    {
        scanf("%d%d%d", &op, &x, &y);
        (op == 1) ? update(x, y) : query(x, y);
    }
    return 0;
}
你当前正在回复 博客/题目
存在问题!