线段树日记

佚名 6年前 (2019-05-09) 随笔 1891人围观抢沙发百度已收录

因为记笔记是很不好玩的事情……

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

https://www.luogu.org/recordnew/show/18875922

我写的第一颗线段树，支持单点修改、查询区间和，常数很大。

——2019.5.8晚上

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 struct Node{
 5     int l , r;
 6     int val;
 7 }t[500001 << 3];
 8 int a[500001], n, m;
 9 void build(int ind, int l, int r) {
10     if(l == r) {
11         t[ind].l = l;
12         t[ind].r = r;
13         t[ind].val = a[l];
14         return;
15     }
16     t[ind].l = l;
17     t[ind].r = r;
18     int mid = (l + r) >> 1;
19     build(ind << 1, l, mid);
20     build((ind << 1) + 1, mid + 1, r);
21     t[ind].val = t[ind << 1].val + t[(ind << 1) + 1].val;
22     return;
23 }
24 
25 //void search(int ind) {
26 //    cout << t[ind].l << "<->" << t[ind].r << '\n'; 
27 //    if(t[ind << 1].val) search(ind << 1);
28 //    if(t[(ind << 1) + 1].val) search((ind << 1) + 1);
29 //}
30 //第一次写， 很好奇地先序遍历了一下 
31 
32 void updata(int x, int val, int ind) {
33     //cout << t[ind].l << '-' << t[ind].r << '\n';
34     if(t[ind].l == t[ind].r) {
35         t[ind].val += val;
36         return;
37     }
38     int mid = (t[ind].l + t[ind].r) / 2;
39     if(x > mid) {
40         updata(x, val, (ind << 1) + 1);
41     }
42     else {
43         updata(x, val, ind << 1);
44     }
45     t[ind].val += val;
46 }
47 
48 int ask(int x, int y, int ind) {
49     if(t[ind].l == t[ind].r) return t[ind].val;
50     int mid = (t[ind].l + t[ind].r) >> 1;
51     if(x <= mid && y > mid) return ask(x , mid, ind << 1) + ask(mid + 1, y, (ind << 1) + 1);
52     else if(x <= mid && y <= mid) {
53         return ask(x, y, ind << 1);
54     }
55     else return ask(x, y, (ind << 1) + 1);
56 }
57 
58 int main() {
59     cin >> n >> m;
60     for(register int i = 1; i <= n; ++i) {
61         scanf("%d", &a[i]);
62     }
63     build(1, 1, n);
64 //    search(1);
65     int oper = 0, x = 0, y = 0, k = 0;
66     for(int i = 1; i <= m; ++i) {
67         scanf("%d", &oper);
68         switch(oper) {
69             case 1:
70                 scanf("%d%d", &x, &k);
71                 updata(x,k,1);
72                 break;
73             case 2:
74                 scanf("%d%d", &x, &y);
75                 cout << ask(x,y,1) << '\n';
76                 break;
77         }
78     }
79     return 0;
80 }

https://www.luogu.org/recordnew/show/18880248

第二颗线段树！支持区间加和、单点查询数值，这次没有超时。

——2019.5.9上午

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cctype>
 4 //对于100%的数据：N<=500000，M<=500000 区间加，单点查询 
 5 using namespace std;
 6 int read() {
 7     char c = getchar();
 8     int x = 0, f = 1;
 9     while(!isdigit(c)) {
10         if(c == '-') f = -1;
11         c = getchar();
12     }
13     while(isdigit(c)) {
14         x = x*10 + c - '0';
15         c = getchar();
16     }
17     return x * f;
18 }
19 struct Node{
20     int l, r;
21     int val, tag;
22 }t[500000 << 1 + 1];
23 int n, m, a[500001];
24 
25 void build(int ind, int left, int right) {
26     if(left == right) {
27         t[ind].l = left;
28         t[ind].r = right;
29         t[ind].val = a[left];
30         return;
31     }
32     int mid = (left + right) >> 1;
33     t[ind].l = left;
34     t[ind].r = right;
35     build(ind << 1, left, mid);
36     build((ind<<1) + 1, mid + 1, right);
37     t[ind].val = t[ind << 1].val + t[(ind<<1) + 1].val;
38     return;
39 }
40 
41 void updata(int left, int right, int value, int ind) {
42     if(left == t[ind].l && right == t[ind].r) {
43         t[ind].tag += value;
44         return;
45     }
46     int mid = (t[ind].l + t[ind].r) >> 1;
47     if(left > mid) updata(left, right, value, (ind << 1) + 1);
48     else
49     if(right < mid+1) updata(left, right, value, ind << 1);
50     else {
51         updata(left, mid, value, ind << 1);
52         updata(mid + 1, right, value, (ind << 1) + 1);
53     }
54     return;
55 }
56 
57 int ask(int x, int ind) {
58     if(t[ind].l == t[ind].r) {
59         t[ind].val += t[ind].tag;
60         t[ind].tag = 0;
61         return t[ind].val;
62     }
63     t[ind << 1].tag += t[ind].tag;
64     t[(ind << 1) + 1].tag += t[ind].tag;
65     t[ind].val += t[ind].tag;
66     t[ind].tag = 0;
67     int mid = (t[ind].l + t[ind].r) >> 1;
68     if(x > mid) return ask(x, (ind << 1) + 1);
69     else return ask(x, ind << 1);
70 }
71 
72 int main() {
73     n = read();
74     m = read();
75     for(int i = 1; i <= n; ++i) {
76         a[i] = read();
77     }
78     build(1,1,n);
79     int oper, x, y, k;
80     for(int i = 1; i <= m; ++i) {
81         oper = read();
82         switch(oper) {
83             case 1:
84                 x = read(), y = read(), k = read();
85                 updata(x, y, k, 1); break;
86             case 2:
87                 x = read();
88                 cout << ask(x,1) << '\n';
89                 break;
90         }
91     }
92     return 0;
93 }