Akira的OI(咸鱼)圈

树状数组

算法
Word count: 431 / Reading time: 3 min
2018/08/18 Share

先占个坑，以后再补(挠头)

树状数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define ll long long
#define maxn 1000001
using namespace std;
inline int read()
{
    int l=0,w=1;
    char ch=0;
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        l=(l<<3)+(l<<1)+(ch^'0');
        ch=getchar();
    }
    return w*l;
}
int t[maxn],n,m;
void add(int x,int k)
{
    while(x<=n)
        t[x]+=k,x+=x&(-x);
}
int sum(int x)
{
    int ans=0;
    while(x>0)
        ans+=t[x],x-=x&(-x);
    return ans;
}
int main()
{
    int x,y,k;
    n=read(),m=read();
    for(int i=1;i<=n;i++)
        x=read(),add(i,x);
    while(m--)
    {
        x=read(),y=read(),k=read();
        if(x==1)
            add(y,k);
        else
            printf("%d\n",sum(k)-sum(y-1));
    }
    return 0;
}

差分树状数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define ll long long
#define maxn 500005
using namespace std;
inline int read()
{
    int l=0,w=1;
    char ch=0;
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        l=(l<<3)+(l<<1)+(ch^'0');
        ch=getchar();
    }
    return w*l;
}
int a[maxn],c[maxn],n;
void add(int x,int k)
{
    while(x<=n)
        c[x]+=k,x+=x&(-x);
}
int sum(int x)
{
    int ans=0;
    while(x>0)
        ans+=c[x],x-=x&(-x);
    return ans;
}
int main()
{
    int m,pre=0,x,y,k;
    n=read(),m=read();
    for(int i=1;i<=n;i++)
    {
        a[i]=read();
        add(i,a[i]-pre);
        pre=a[i];
    }
    while(m--)
    {   
        pre=read(),x=read();
        if(pre==1)
        {
            y=read(),k=read();
            add(x,k);
            add(y+1,-k);
        }
        else
        printf("%d\n",sum(x));
    }
    return 0;
}

原文作者: Akira

原文链接: https://akira-1231.github.io/2018/08/18/树状数组/

发表日期: 八月 18日 2018, 9:57:39 上午

版权声明: 本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. 树状数组
  2. 2. 差分树状数组
Total : 11
2018
题解 算法 杂记