遇到这种需要维护区间的题目，我们一般就会想到强大的线段树或树状数组，这里我们就使用码量较小的树状数组。

但树状数组仅支持单点修改与区间查询，而这里需要支持区间修改与区间查询。这可怎么办呢？这时，我们可以采用**括号序列**来解决。

对于这个题，我们用两个树状数组a，b来维护左括号与右括号，若要在区间[l,r]种树，则将a[l]添个左括号（即upd_a(l,1);），将b[r]添个右括号（即upd_b(r,1);）。区间查询时，就只要统计r之前（包含r）有多少个左括号（即sum(r);），再统计l之前（不包含l）有多少个右括号（即sum(l-1);），把两个结果相减，便可得到[l,r]之间有多少种树了。

没什么需要注意的地方，代码也十分好写。

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

int n,m,a[50031],b[50031];

//树状数组全家桶
int lowbit(int x){ return x&(-x); }
void upd_a(int id,int x){ for(int i=id;i<=n;i+=lowbit(i)) a[i]+=x;  }
void upd_b(int id,int x){ for(int i=id;i<=n;i+=lowbit(i)) b[i]+=x;  }
void upd(int l,int r){ upd_a(l,1),upd_b(r,1); }
int sum_a(int t){ int ans=0; for(int i=t;i;i-=lowbit(i)) ans+=a[i]; return ans; }
int sum_b(int t){ int ans=0; for(int i=t;i;i-=lowbit(i)) ans+=b[i]; return ans; }
int qry(int l,int r){ return sum_a(r)-sum_b(l-1); }

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

    for(int i=1;i<=m;i++){
        int op,l,r; scanf("%d",&op);

        if(op==1){ scanf("%d%d",&l,&r); upd(l,r); } //区间修改
        
        else{ scanf("%d%d",&l,&r); printf("%d\n",qry(l,r)); } //区间查询
    }
    return 0; //完结撒花~
}

参考文献：

https://www.cnblogs.com/shadowland/p/5870395.html

https://zhuanlan.zhihu.com/p/93795692

参考https://www.cnblogs.com/shadowland/p/5870395.html
这篇写的很好
用树状数组和线段树都可以，只要可以维护区间加法查询就可以了 - 原理是用两个数据结构分别维护每个树种区间的左端点和右端点，
设查询的区间为tl, tr
一个查询区间里存在的树种的个数（多少个不同的树种区间在我们的区间里）= [1, tr]上左端点的个数 - [1, tl - 1]上右端点的个数。这样就是所有[1, tr]上的区间里有所覆盖的树区间，去掉 只出现在[1, tl - 1]上的树区间，剩下的区间就是所有涉及到[tl, tr]的树区间辣！压力马斯内！（赞赏）

经验教训
1. 又没有好好读题，只有单个更新和区间查询，和懒更新毛线的关系都没有，不要多写。。。
2. 刚开始Runtime Error,后来一想线段树至少要开数据规模x4吧，居然没写。。。
3. 快读写了居然用了cin??? 哈 哈。对比一下快了20多ms，快读还是狠滴

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

int n, m;

int read() {
    int f = 1, x = 0;
    char c; c = getchar();
    if (c == '-') { f = -1; c = getchar(); }
    while ('0' <= c && c <= '9') {
        x *= 10;
        x += c - '0';
        c = getchar();
    }
    return x * f;
}

struct Node {
    int l, r, val;
    Node& operator++() { 
        val++; 
        return *this;
    }
};

const int MAXN = (5e4 + 500) * 10;

struct SegmentTree {
    int cnt, root;
    Node nodes[MAXN];

    SegmentTree() {
        getNode(root);
    }

    int getNode(int& x) {
        if (!x) { return (x = ++cnt); }
        return x;
    }

    bool exist(int x) {
        if (!x) return false;
        return true;
    }

    void add(int p, int t, int l, int r) {
        Node& curr = nodes[p];
        if (r < t || t < l || r < l) { return; }
        if (l == r && l == t) { ++curr; return; }
        else {
            int mid = (l + r) / 2;
            if (t <= mid) { add(getNode(curr.l), t, l, mid); }
            else if (t > mid) { add(getNode(curr.r), t, mid + 1, r); }
        }
        curr.val = nodes[curr.l].val + nodes[curr.r].val;
    }

    int query(int p, int tl, int tr, int l, int r) {
        Node& curr = nodes[p];
        if (tl <= l && r <= tr) return curr.val;
        if (r < tl || tr < l || !exist(p) || r < l) return 0;
        else {
            int mid = (l + r) / 2, sum = 0;
            if (tl <= mid) { sum += query(curr.l, tl, tr, l, mid); }
            if (tr > mid) { sum += query(curr.r, tl, tr, mid + 1, r); }
            return sum;
        }
    }

} lb, rb; //left bracket, right bracket

int main() {
    n = read(); m = read();
    for (int i = 1; i <= m; i++) {
        int c, param1, param2;
        c = read(); param1 = read(); param2 = read();
        if (c == 1) {
                lb.add(lb.root, param1, 1, n);
                rb.add(rb.root, param2, 1, n);
        } else {
            cout << lb.query(lb.root, 1, param2, 1, n) - rb.query(rb.root, 1, param1 - 1, 1, n) << endl;
        }
    }
    return 0;
}

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;

namespace dts
{
    struct st_node
    {
        int l,r,mid,suml,sumr;
    };
    
    int n,m;
    st_node st[(1<<18)+2];
    #define lc(now) ((now)<<1)
    #define rc(now) (((now)<<1)|1)
    
    void st_build(int now,int l,int r)
    {
        st[now].l=l,st[now].r=r;
        st[now].suml=st[now].sumr=0;
        if (l<r)
        {
            st[now].mid=(l+r)>>1;
            st_build(lc(now),l,st[now].mid);
            st_build(rc(now),st[now].mid+1,r);
        }
    }
    
    void st_update(int now,int pos,int task)//l:task=1 r:task=-1
    {
        if (st[now].l==pos&&pos==st[now].r)
        {
            if (task==1)
                st[now].suml++;
            else if (task==-1)
                st[now].sumr--;
        }
        else
        {
            if (pos<=st[now].mid)
                st_update(lc(now),pos,task);
            else if (st[now].mid+1<=pos)
                st_update(rc(now),pos,task);
            if (task==1)
                st[now].suml=st[lc(now)].suml+st[rc(now)].suml;
            else if (task==-1)
                st[now].sumr=st[lc(now)].sumr+st[rc(now)].sumr;
        }
    }
    
    int st_ask(int now,int l,int r,int task)//l:task=1 r:task=-1
    {
        if (st[now].l==l&&r==st[now].r)
        {
            if (task==1)
                return st[now].suml;
            else if (task==-1)
                return st[now].sumr;
        }
        else
        {
            if (r<=st[now].mid)
                return st_ask(lc(now),l,r,task);
            else if (st[now].mid+1<=l)
                return st_ask(rc(now),l,r,task);
            else
                return st_ask(lc(now),l,st[now].mid,task)+st_ask(rc(now),st[now].mid+1,r,task);
        }
    }
    
    void main()
    {
        scanf("%d%d",&n,&m);
        st_build(1,1,n);
        for (int i=1;i<=m;i++)
        {
            int K,l,r;
            scanf("%d%d%d",&K,&l,&r);
            if (K==1)
            {
                st_update(1,l,1);
                if (r+1<=n)
                    st_update(1,r+1,-1);
            }
            else if (K==2)
            {
                int suml=st_ask(1,1,r,1),sumr=st_ask(1,1,l,-1);
                printf("%d\n",suml+sumr);
            }
        }
    }
}

int main()
{
    dts::main();
}

树状数组解

#include <iostream>
#include <cstdio>
#define ll long long
#define rll register long long
using namespace std;
const int MAXN=5e4+5;
ll n,m,c1[MAXN],c2[MAXN];
inline ll lowbit(rll i){return i&(-i);}
inline void update1(rll x,rll value)
{
    for(rll i=x;i<=n;i+=lowbit(i))
        c1[i]+=value;
}
inline ll find1(rll x)
{
    rll res=0;
    for(rll i=x;i;i-=lowbit(i))
        res+=c1[i];
    return res;
}
inline void update2(rll x,rll value)
{
    for(rll i=x;i<=n;i+=lowbit(i))
        c2[i]+=value;
}
inline ll find2(rll x)
{
    rll res=0;
    for(rll i=x;i;i-=lowbit(i))
        res+=c2[i];
    return res;
}
int main()
{
    scanf("%lld%lld",&n,&m);
    for(rll i=1,k,l,r;i<=m;i++)
    {
        scanf("%lld%lld%lld",&k,&l,&r);
        if(k==1)
        {
            update1(l,1);
            update2(r,1);
        }
        else
            printf("%lld\n",find1(r)-find2(l-1));
    }
    return 0；
}

JRX2015U43：树状数组。
http://blog.csdn.net/qq_31640513/article/details/61435432

#include <bits/stdc++.h>
#define maxN 200010 

using namespace std ;
typedef long long QAQ ;

struct Tree{int l , r ; QAQ liml , limr ;};

Tree tr[maxN<<2];

void Build_Tree ( int x , int y , int i ){
    tr[i].l = x ;
    tr[i].r = y ;
    if( x==y )return ;
    else {
        QAQ mid = (tr[i].l + tr[i].r) >> 1 ;
        Build_Tree ( x , mid , i<<1);
        Build_Tree ( mid+1 , y , i<<1|1);
        return ;
    }
}

void Update_left ( int w , int i ){
    if( w==tr[i].l && w==tr[i].r )tr[i].liml++;
    else {
        QAQ mid = (tr[i].l + tr[i].r) >> 1 ;
        if( w>mid )Update_left( w , i<<1|1);else
        if( w<=mid)Update_left( w , i<<1 );
        tr[i].liml = tr[i<<1].liml + tr[i<<1|1].liml ;
    }
}

void Update_right ( int w , int i ){
    if( w==tr[i].l && w==tr[i].r )tr[i].limr++;
    else {
        QAQ mid = (tr[i].l + tr[i].r) >> 1 ;
        if( w>mid )Update_right( w , i<<1|1);else
        if( w<=mid)Update_right( w , i<<1 );
        tr[i].limr = tr[i<<1].limr + tr[i<<1|1].limr ;
    }
}

QAQ Query_left ( int q ,int w ,int i ){
    if( q<=tr[i].l && w>=tr[i].r )return tr[i].liml ;
    else {
        QAQ mid = (tr[i].l + tr[i].r) >> 1 ;
        if ( q>mid )return Query_left ( q , w , i<<1|1);
        else if ( w<=mid ) return Query_left ( q , w , i<<1);
        else return Query_left ( q , w , i<<1|1)+Query_left ( q , w , i<<1);
    }
}

QAQ Query_right ( int q ,int w ,int i ){
    if( q<=tr[i].l && w>=tr[i].r )return tr[i].limr ;
    else {
        QAQ mid = (tr[i].l + tr[i].r) >> 1 ;
        if ( q>mid )return Query_right ( q , w , i<<1|1);
        else if ( w<=mid ) return Query_right ( q , w , i<<1);
        else return Query_right ( q , w , i<<1|1)+Query_right ( q , w , i<<1);
    }
}

int main(){
    int N,M,op,ll,rr ;
    scanf("%d %d",&N,&M);
    Build_Tree ( 1 , N , 1 ) ;
    while(M--){
        scanf("%d%d%d",&op,&ll,&rr);
        if( op==1 ){
            Update_left ( ll , 1);
            Update_right ( rr , 1 );
        }
        else {
            QAQ ans = Query_left( 1 , rr , 1);
            if (ll!=1)ans-=Query_right(1 , ll-1 , 1);
            printf("%I64d\n",ans);
        }
    }
    return 0 ;
}

Horizontal Rule

线段树括号法

线段树解。题目可以理解为求给定区间和多少已知区间相交。那么只需要求出与当前区间不相交的，再减去就好了。具体思路为记录每一个区间的开始点与终端。如果当前区间的终端小于某区间的开始点或当前区间的开始点大于某区间的终端，则该区间与当前区间不相交。

var a:array[0..200000,1..2]{1表示开始点，2表示终端} of longint;

n,m,i,x,y,all,mr,ml,le,ri,k:longint;

Procedure change(l,r,x,pos,num:longint);{记录每一个区间的开始点与终端}

begin

if (pos>r)or(pos=ml then exit(0);

if ml>r then exit(a[x,2]);

le:=searchle(l,(l+r)div 2,2*x);

ri:=searchle((l+r)div 2+1,r,2*x+1);

exit(le+ri);

end;

Function searchri(l,r,x:longint):longint;{寻找右侧不相交区间数}

var le,ri:longint;

begin

if r

#include<stdio.h>

int main()

{

int L, M, i, j, n;

int a[10001], b[10001];

scanf("%d %d",&L, &M); //输入L和M

n = M*2;//循环输入b数组0~n的数据

for(i=0; i<n; i+=2)

{

scanf("%d %d", &b[i], &b[i+1]);

}

for(i=0; i<=L; i++) //循环给a数组L个元素赋值

{

a[i] = i;

}

int r, s;

for(i=0; i<n; i+=2) //遍历访问数组b的各个区间

{

r = b[i]; //区间起始点

s = b[i+1]; //区间终点

for(j=r; j<=s; j++) //把数组b各个区间内元素在数组a中映射为0

{

a[j] = -1;

}

}

int k=0; 

for(i=0; i<=L; i++)

{

if(a[i] != -1)

{

k++; 

}

}

printf("%d", k);

return 0;

}

简单的模板题
开两个树状数组维护即可

#include <iostream>
#include <cstdio>
using namespace std;
const int maxn=500040;
int a[maxn],b[maxn];
int n,m;
int lowbit(int x)
{
    return x&(-x);
}
void add1(int x,int y)
{
    while(x<=n)
    {
        a[x]+=y;
        x+=lowbit(x);
    }
}
void add2(int x,int y)
{
    while(x<=n)
    {
        b[x]+=y;
        x+=lowbit(x);
    }
}

int sum1(int x)
{
    int ans=0;
    while(x>0)
    {
        ans+=a[x];
        x-=lowbit(x);
    }
    return ans;
}
int sum2(int x)
{
    int ans=0;
    while(x>0)
    {
        ans+=b[x];
        x-=lowbit(x);
    }
    return ans;
}
int main(){
    cin>>n>>m;
    while(m--)
    {
        int wzx,x,y;
        scanf("%d",&wzx);
        if(wzx==1)
        {
            scanf("%d %d",&x,&y);
            add1(x,1);
            add2(y,1);
        }
        if(wzx==2)
        {
            scanf("%d%d",&x,&y);
            printf("%d\n",sum1(y)-sum2(x-1));
        }
    }
    return 0;
}

OTL 括号法

树状数组无压力的说-_-

这题看起来和树状数组没什么关系，不过我们通过一定的转化，可以利用树状数组很好地解决这个问题。

我们不妨把所有线段的端点看成括号序列，即把询问的区间[lq,rq]看成在横坐标lq处的一个‘[’和rq处的‘]’, 即把插入的线段[li,ri]看成在横坐标li处的一个‘(’和ri处的‘)’。

稍作分析，我们不难发现，最后的答案等于‘]’左边‘(’的个数减去‘[’左边‘)’的个数。

那么我们现在做的就是对某个点做修改，对某个前缀求和。我们就可以很容易想到树状数组的做法：

1.建立两个树状数T1和T2，分别维护‘(’和‘)’。

2.若K=1，读入li,ri，plusT1(li,1)，plusT2(ri,1)。

3.若K=2，读入lq,rq，sumT1(rq)-sumT2(lq-1)

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 9ms

├ 测试数据 06：答案正确... 56ms

├ 测试数据 07：答案正确... 586ms

├ 测试数据 08：答案正确... 1117ms

├ 测试数据 09：答案正确... 2802ms

├ 测试数据 10：答案正确... 2926ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：7496ms

括号法AC，编的很烂，没有什么优化……不过AC就好

还问一下，限时不是1s么，不应该早超时了么？……

为什么我就用了一个树状数组?

program tree;

var

c:array[1..50000]of longint;

i,j,k,l,n,m:longint;

procedure add(k,p:longint);

var

t:longint;

begin

t:=p;

while t0 do

begin

inc(getsum,c[t]);

t:=t-t and(-t);

end;

end;

procedure deal(j:longint);

var l,r,a,b,t,a1,b1,t1:longint;

begin

if j=1 then

begin

readln(l,r);

add(1,l);

add(50001,r);

end;

if j=2 then

begin

readln(l,r);

a:=getsum(l-1);b:=getsum(r);t:=getsum(n);

a1:=a mod 50001-a div 50001;b1:=(t-b) div 50001-(t-b) mod 50001;

t1:=(b-a)-a1*50001-b1;

writeln(t1 div 50002+a1+b1);

end;

end;

begin

readln(n,m);

for i:=1 to m do

begin

read(j);

deal(j);

end;

end.

又写了个线段树之后我就知道我有多么弱了

5次WA,最后发现查询的时候边界问题

同意楼下，我一开始也意味要拔了重种..

看错题目，以为后种的树会覆盖掉前面的，于是线段树，pass括号法……

发现自己沙茶了，可写了好一会的线段树也舍不得删啊，改之……

├ 测试数据 07：答案正确... 25ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 25ms

├ 测试数据 10：答案正确... 25ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：75ms

比较慢额……

program Project1;

var c,d:array[0..50000] of longint;

i,k,n,m,cc,st,en,ansa,ansb:longint;

begin

readln(n,m);

for i:=1 to m do

begin

readln(cc,st,en);

if cc=1 then

begin

k:=st;

while k0 do

begin

inc(ansb,d[k]);

dec(k,k and (-k));

end;

writeln(ansa-ansb);

end;

end;

end.

为什么wa了3个？

树状数组好牛B的样子，咱看了论文再来AC

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

program p1448;

var

n,m,a,b,k,i:longint;

x,y:array [1..50000] of longint;

function low(x:longint):longint;

begin

low:=x and (x xor (x-1));

end;

procedure work(a:longint);

begin

while a0 do

begin

t:=t+y[a];

dec(a,low(a));

end;

out2:=t;

end;

begin

readln(n,m);

for i:=1 to m do

begin

readln(k,a,b);

if k=1 then begin

work(a);

work2(b);

end;

if k=2 then

writeln(out1(b)-out2(a-1));

end;

end.

贴一个树状数组吧

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

树状数组

佩服佩服

纯模拟都能过.....

Easy无敌！！！

By fjxmlhx

---|---|---|---|---|---|---|---|---|---|---|---|--

在l处添加一个左括号，在y处添加一个右括号。

ans=1~r的左括号-1~l-1的右括号