<commit_before>﻿---
layout: post
title: 线段树专辑（持续更新中。。。）
category: ACM
tags: 线段树
keywords:
description:
---

###简介
线段树是一种二叉树，把整个区间分为一个个小的区间，树中每个节点对应一个区间，用于处理区间上的修改，查询操作。两者的时间复杂度可以到到**O(logN)**。若父区间为[l,r]，那么左右区间分别为[l,(l + r) >> 1],[(l + r) / 2 + 1,r]。

###数据结构
我所用的是结构体来保存节点信息

```cpp
struct Node{
    int l,r;
    elemtype some_other_info,...;
}
```
###基础操作

```cpp
void build(int k,int l,int r){
    node[k].l = l,node[k].r = r;
    ....;

    if(l == r) {
        node[k].flag = 1;
        return;
    }

    int mid = (l + r) >> 1;
    build(k << 1,l,mid),build(k<<1|1,mid + 1,r);
    ...;
}
```

```cpp
void updata(int k,int l,int r,...){
    if(node[k].l == l && node[k].r == r){
        ....;
        ....;
        ....;
        return;
    }
    pushDown(k);
    ...;

    int mid = (node[k].l + node[k].r) >> 1;
    if(mid < l) updata(k << 1|1,l,r,...);
    else if(mid >= r) updata(k << 1,l,r,...);
    else updata(k << 1,l,mid,...),updata(k << 1|1,mid + 1,r,...);
    pushUp(k);
}
```

```cpp
elemType query(int k,int l,int r){
    if(node[k].l == l && node[k].r == r){
        ...;
        ...;
        ...;
        return ...;
    }
    pushDown(k);
    ...;

    int mid = (node[k].l + node[k].r) >> 1;
    if(mid < l) return query(k << 1|1,l,r);
    else if(mid >= r) return query(k << 1,l,r);
    else return qeury(k << 1,l,mid,...) + query(k << 1|1,mid + 1,r);
    pushUp(k);
}
```

###关键操作
关键操作主要是**pushUp(),pushDown()**:

```cpp
inline void pushUp(int k){
    if(node[k<<1] and node[k<<1|1] fit some conditions)
        update node[k];
    ...;
}
```

```cpp
inline  void pushDown(int k){
    if(node[k] fit some conditions)
        update node[k<<1] and node[k<<1|1];
    update node[k];
    ...;
}
```

###适合解决的问题

<pre>
    1.单点更新，区间查询；
    2.区间更新，单点查询；
    3.区间更新，区间查询；
</pre>

###一些题目

#### 1.[HDOJ 4578](http://acm.hdu.edu.cn/showproblem.php?pid=4578)

#####题意

给定长度为n一个初始序列，一开始所有的值都为0，现有四种操作：

<pre>
    1,L,R,C: 区间[L, R]内所有的数都加上C；
    2,L,R,C: 区间[L, R]内所有的数都乘上C；
    3,L,R,C: 区间[L, R]所有的数都变成C；
    4,L,R,P: 查询区间[L , R] 所有数的P次幂之和，结果对 10007 取模。
</pre>

#####思路

对于操作1,2,3维护一个区间内是否只有一种数，且该数是都少。那么查询（操作4）的时候若满足区间内只有一个数，就可以在**O(1)**时间复杂度内求出多有数P次幂之和。维护的时间复杂度为**O(n)**

#####代码

```cpp
#include<set>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#define LL int
using namespace std;
const int MAXN = 1e5 + 10;
struct Node{
    int l,r,flag;
    LL c;
};
Node node[MAXN<<2];
inline void pushDown(int k){
    if(node[k].flag == 0) return;
    node[k<<1].flag = 1,node[k<<1|1].flag = 1;
    node[k<<1].c = node[k].c,node[k<<1|1].c = node[k].c;
    node[k].flag = 0;
}
inline void pushUp(int k){
    if(node[k<<1].c == node[k<<1|1].c && node[k<<1].flag && node[k<<1|1].flag) {
        node[k].flag = 1;
        node[k].c = node[k<<1].c;
    }else node[k].flag = 0;
}
void build(int k,int l,int r){
    node[k].l = l,node[k].r = r,node[k].flag = 0,node[k].c = 0;
    if(l == r) {
        node[k].flag = 1;
        return;
    }
    int mid = (l + r) >> 1;
    build(k << 1,l,mid),build(k<<1|1,mid + 1,r);
    pushUp(k);
}
void updata(int k,int l,int r,int t,int c){
    if(node[k].l == l && node[k].r == r && node[k].flag == 1){
        if(t == 1) node[k].c += c,node[k].c %= 10007;
        else if(t == 2) node[k].c *= c,node[k].c %= 10007;
        else if(t == 3) node[k].c = c;
        return;
    }
    pushDown(k);
    int mid = (node[k].l + node[k].r) >> 1;
    if(mid < l) updata(k << 1|1,l,r,t,c);
    else if(mid >= r) updata(k << 1,l,r,t,c);
    else updata(k<<1,l,mid,t,c),updata(k<<1|1,mid+1,r,t,c);
    pushUp(k);
}
LL query(int k,int l,int r,int t){
    if(node[k].flag) {
        LL ans = 1,tmp = node[k].c % 10007,len = (r - l + 1) % 10007;
        for(int i = 0;i < t;i ++) ans *= tmp,ans %= 10007;
        ans *= len,ans %= 10007;
        return ans;
    }
    pushDown(k);
    int mid = (node[k].l + node[k].r) >> 1;
    if(mid < l) return query(k<<1|1,l,r,t);
    else if(mid >= r) return query(k<<1,l,r,t);
    else return (query(k<<1,l,mid,t) + query(k<<1|1,mid + 1,r,t)) % 10007;
    pushUp(k);
}
int main(){
    int n,m,a,b,c,d;
    #ifndef ONLINE_JUDGE
    freopen("in.cpp","r",stdin);
    #endif // ONLINE_JUDGE
    while(~scanf("%d%d",&n,&m) && (n + m)){
        build(1,1,n);
        while(m--){
            scanf("%d%d%d%d",&a,&b,&c,&d);
            if(a != 4) updata(1,b,c,a,d);
            else printf("%d\n",query(1,b,c,d));
        }
    }
    return 0;
}
```

#### 2.[Codeforces 380C](http://codeforces.com/problemset/problem/380/C)

#####题意

给定一个括号串S( 1 <= len(s) <= 1e6),和询问次数m (1 <= m  <= 1e5)每次询问区间[L, R]内有多少个括号配对，时间限制1s。

#####思路

最简单的方法就是用栈模拟，时间复杂度最坏情况下是**O(len(s)*m)**，无疑会超时。用线段树，维护一个区间内有多少左括号和右括号，同时记录该区间已经匹配的长度。**向上更新的时候，左右括号直接加即可，对于更新已经匹配的长度：为孩子区间的相加，同时由于左区间的右括号和又区间的左括号会组成合法的匹配，也需要加上，取二者的最小值即可**。

#####代码

```cpp
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN = 1e6+10;
struct Node{
    int l,r,len,lcnt,rcnt;
}node[MAXN << 2];
struct St{
    int l,r,len;
    St(int ll,int rr,int en){l = ll,r = rr,len = en;}
};
char str[MAXN];
inline void pushUp(int k){
    node[k].len = node[k<<1].len + node[k<<1|1].len;
    int rcnt = node[k<<1].rcnt - node[k<<1].len/2;
    int lcnt = node[k<<1|1].lcnt - node[k<<1|1].len/2;
    node[k].len += 2*min(lcnt,rcnt);
    node[k].lcnt = node[k<<1].lcnt + node[k<<1|1].lcnt;
    node[k].rcnt = node[k<<1].rcnt + node[k<<1|1].rcnt;
}
void build(int k,int l,int r){
    node[k].l = l,node[k].r = r;
    node[k].lcnt = node[k].rcnt = 0;
    if(l == r){
        if(str[l-1] == '(') node[k].rcnt = 1;
        else node[k].lcnt = 1;
        return;
    }
    int mid = (l + r) >> 1;
    build(k<<1,l,mid),build(k<<1|1,mid+1,r);
    pushUp(k);
}
St query(int k,int l,int r){
    if(node[k].l == l && node[k].r == r) return St(node[k].lcnt,node[k].rcnt,node[k].len);
    int mid = (node[k].l + node[k].r) >> 1;
    if(mid < l) return query(k << 1|1,l,r);
    else if(mid >= r) return query(k << 1,l,r);
    else{
        St t1 = query(k<<1,l,mid),t2 = query(k<<1|1,mid+1,r);
        int ans = t1.len + t2.len + 2*min(t1.r-t1.len/2,t2.l-t2.len/2);
        return St(t1.l+t2.l,t1.r+t2.r,ans);
    }
}
int main(){
    //freopen("in.cpp","r",stdin);
    scanf("%s",str);
    build(1,1,strlen(str));
    int m,l,r;
    scanf("%d",&m);
    while(m--){
        scanf("%d%d",&l,&r);
        printf("%d\n",query(1,l,r).len);
    }
    return 0;
}
```


<commit_msg>Update 2014-09-24-segTree.md<commit_after>﻿---
layout: post
title: 线段树专辑
category: ACM
tags: 线段树
keywords:
description:
---

###简介
线段树是一种二叉树，把整个区间分为一个个小的区间，树中每个节点对应一个区间，用于处理区间上的修改，查询操作。两者的时间复杂度可以到到**O(logN)**。若父区间为[l,r]，那么左右区间分别为[l,(l + r) >> 1],[(l + r) / 2 + 1,r]。

###数据结构
我所用的是结构体来保存节点信息

```cpp
struct Node{
    int l,r;
    elemtype some_other_info,...;
}
```
###基础操作

```cpp
void build(int k,int l,int r){
    node[k].l = l,node[k].r = r;
    ....;

    if(l == r) {
        node[k].flag = 1;
        return;
    }

    int mid = (l + r) >> 1;
    build(k << 1,l,mid),build(k<<1|1,mid + 1,r);
    ...;
}
```

```cpp
void updata(int k,int l,int r,...){
    if(node[k].l == l && node[k].r == r){
        ....;
        ....;
        ....;
        return;
    }
    pushDown(k);
    ...;

    int mid = (node[k].l + node[k].r) >> 1;
    if(mid < l) updata(k << 1|1,l,r,...);
    else if(mid >= r) updata(k << 1,l,r,...);
    else updata(k << 1,l,mid,...),updata(k << 1|1,mid + 1,r,...);
    pushUp(k);
}
```

```cpp
elemType query(int k,int l,int r){
    if(node[k].l == l && node[k].r == r){
        ...;
        ...;
        ...;
        return ...;
    }
    pushDown(k);
    ...;

    int mid = (node[k].l + node[k].r) >> 1;
    if(mid < l) return query(k << 1|1,l,r);
    else if(mid >= r) return query(k << 1,l,r);
    else return qeury(k << 1,l,mid,...) + query(k << 1|1,mid + 1,r);
    pushUp(k);
}
```

###关键操作
关键操作主要是**pushUp(),pushDown()**:

```cpp
inline void pushUp(int k){
    if(node[k<<1] and node[k<<1|1] fit some conditions)
        update node[k];
    ...;
}
```

```cpp
inline  void pushDown(int k){
    if(node[k] fit some conditions)
        update node[k<<1] and node[k<<1|1];
    update node[k];
    ...;
}
```

###适合解决的问题

<pre>
    1.单点更新，区间查询；
    2.区间更新，单点查询；
    3.区间更新，区间查询；
</pre>

###一些题目

#### 1.[HDOJ 4578](http://acm.hdu.edu.cn/showproblem.php?pid=4578)

#####题意

给定长度为n一个初始序列，一开始所有的值都为0，现有四种操作：

<pre>
    1,L,R,C: 区间[L, R]内所有的数都加上C；
    2,L,R,C: 区间[L, R]内所有的数都乘上C；
    3,L,R,C: 区间[L, R]所有的数都变成C；
    4,L,R,P: 查询区间[L , R] 所有数的P次幂之和，结果对 10007 取模。
</pre>

#####思路

对于操作1,2,3维护一个区间内是否只有一种数，且该数是都少。那么查询（操作4）的时候若满足区间内只有一个数，就可以在**O(1)**时间复杂度内求出多有数P次幂之和。维护的时间复杂度为**O(n)**

#####代码

```cpp
#include<set>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#define LL int
using namespace std;
const int MAXN = 1e5 + 10;
struct Node{
    int l,r,flag;
    LL c;
};
Node node[MAXN<<2];
inline void pushDown(int k){
    if(node[k].flag == 0) return;
    node[k<<1].flag = 1,node[k<<1|1].flag = 1;
    node[k<<1].c = node[k].c,node[k<<1|1].c = node[k].c;
    node[k].flag = 0;
}
inline void pushUp(int k){
    if(node[k<<1].c == node[k<<1|1].c && node[k<<1].flag && node[k<<1|1].flag) {
        node[k].flag = 1;
        node[k].c = node[k<<1].c;
    }else node[k].flag = 0;
}
void build(int k,int l,int r){
    node[k].l = l,node[k].r = r,node[k].flag = 0,node[k].c = 0;
    if(l == r) {
        node[k].flag = 1;
        return;
    }
    int mid = (l + r) >> 1;
    build(k << 1,l,mid),build(k<<1|1,mid + 1,r);
    pushUp(k);
}
void updata(int k,int l,int r,int t,int c){
    if(node[k].l == l && node[k].r == r && node[k].flag == 1){
        if(t == 1) node[k].c += c,node[k].c %= 10007;
        else if(t == 2) node[k].c *= c,node[k].c %= 10007;
        else if(t == 3) node[k].c = c;
        return;
    }
    pushDown(k);
    int mid = (node[k].l + node[k].r) >> 1;
    if(mid < l) updata(k << 1|1,l,r,t,c);
    else if(mid >= r) updata(k << 1,l,r,t,c);
    else updata(k<<1,l,mid,t,c),updata(k<<1|1,mid+1,r,t,c);
    pushUp(k);
}
LL query(int k,int l,int r,int t){
    if(node[k].flag) {
        LL ans = 1,tmp = node[k].c % 10007,len = (r - l + 1) % 10007;
        for(int i = 0;i < t;i ++) ans *= tmp,ans %= 10007;
        ans *= len,ans %= 10007;
        return ans;
    }
    pushDown(k);
    int mid = (node[k].l + node[k].r) >> 1;
    if(mid < l) return query(k<<1|1,l,r,t);
    else if(mid >= r) return query(k<<1,l,r,t);
    else return (query(k<<1,l,mid,t) + query(k<<1|1,mid + 1,r,t)) % 10007;
    pushUp(k);
}
int main(){
    int n,m,a,b,c,d;
    #ifndef ONLINE_JUDGE
    freopen("in.cpp","r",stdin);
    #endif // ONLINE_JUDGE
    while(~scanf("%d%d",&n,&m) && (n + m)){
        build(1,1,n);
        while(m--){
            scanf("%d%d%d%d",&a,&b,&c,&d);
            if(a != 4) updata(1,b,c,a,d);
            else printf("%d\n",query(1,b,c,d));
        }
    }
    return 0;
}
```

#### 2.[Codeforces 380C](http://codeforces.com/problemset/problem/380/C)

#####题意

给定一个括号串S( 1 <= len(s) <= 1e6),和询问次数m (1 <= m  <= 1e5)每次询问区间[L, R]内有多少个括号配对，时间限制1s。

#####思路

最简单的方法就是用栈模拟，时间复杂度最坏情况下是**O(len(s)*m)**，无疑会超时。用线段树，维护一个区间内有多少左括号和右括号，同时记录该区间已经匹配的长度。**向上更新的时候，左右括号直接加即可，对于更新已经匹配的长度：为孩子区间的相加，同时由于左区间的右括号和又区间的左括号会组成合法的匹配，也需要加上，取二者的最小值即可**。

#####代码

```cpp
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN = 1e6+10;
struct Node{
    int l,r,len,lcnt,rcnt;
}node[MAXN << 2];
struct St{
    int l,r,len;
    St(int ll,int rr,int en){l = ll,r = rr,len = en;}
};
char str[MAXN];
inline void pushUp(int k){
    node[k].len = node[k<<1].len + node[k<<1|1].len;
    int rcnt = node[k<<1].rcnt - node[k<<1].len/2;
    int lcnt = node[k<<1|1].lcnt - node[k<<1|1].len/2;
    node[k].len += 2*min(lcnt,rcnt);
    node[k].lcnt = node[k<<1].lcnt + node[k<<1|1].lcnt;
    node[k].rcnt = node[k<<1].rcnt + node[k<<1|1].rcnt;
}
void build(int k,int l,int r){
    node[k].l = l,node[k].r = r;
    node[k].lcnt = node[k].rcnt = 0;
    if(l == r){
        if(str[l-1] == '(') node[k].rcnt = 1;
        else node[k].lcnt = 1;
        return;
    }
    int mid = (l + r) >> 1;
    build(k<<1,l,mid),build(k<<1|1,mid+1,r);
    pushUp(k);
}
St query(int k,int l,int r){
    if(node[k].l == l && node[k].r == r) return St(node[k].lcnt,node[k].rcnt,node[k].len);
    int mid = (node[k].l + node[k].r) >> 1;
    if(mid < l) return query(k << 1|1,l,r);
    else if(mid >= r) return query(k << 1,l,r);
    else{
        St t1 = query(k<<1,l,mid),t2 = query(k<<1|1,mid+1,r);
        int ans = t1.len + t2.len + 2*min(t1.r-t1.len/2,t2.l-t2.len/2);
        return St(t1.l+t2.l,t1.r+t2.r,ans);
    }
}
int main(){
    //freopen("in.cpp","r",stdin);
    scanf("%s",str);
    build(1,1,strlen(str));
    int m,l,r;
    scanf("%d",&m);
    while(m--){
        scanf("%d%d",&l,&r);
        printf("%d\n",query(1,l,r).len);
    }
    return 0;
}
```



{'fraction_non_alphanumeric': 0.251681744374855, 'fraction_numerical': 0.035722570169334264, 'mean_word_length': 2.7598837209302327, 'pattern_counts': {'":': 0, '<': 257, '<?xml version=': 0, '>': 79, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4646699', 'n_tokens_mistral': 6913, 'n_tokens_neox': 6898, 'n_words': 1055}