标签：trie ll read while 数据结构 节点 define

单调栈

单调栈和单调队列都是思维难度比较大的数据结构，但只要想明白了就会觉得很简单。
要理解单调栈，首先得明白“单调”是指它存储的内容存在单调性，而不是指它简单。

模板题（AcWing.830）

题目描述

给定一个长度为 \(N\) 的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出 \(−1\)。

样例

in：

5
3 4 2 7 5

out:

-1 3 -1 2 2

单调栈实现

思路

首先想暴力做法（毕竟暴力是灵感的源泉），就是每个数往左遍历，直到找到比它小的数，就输出。

#include <bits/stdc++.h>
#define ll long long
#define rll register ll
#define cll const ll
#define N 100005
using namespace std;
inline ll read()
{
    rll x=0;bool f=1;static char c=getchar();
    while(!isdigit(c)){if(c=='-') f=0;c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    return f?x:-x;
}
inline void write(ll x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+48);
}
ll n=read(),a[N];
int main()
{
    for(ll i=1;i<=n;i++)
    {
        a[i]=read();
        if(i==1)
        {
            putchar('-');
            putchar('1');
            putchar(' ');
        }
        for(ll j=i-1;j>=1;j--)
        {
            if(a[j]<a[i])
            {
                write(a[j]),putchar(' ');
                break;
            }
            if(j==1&&a[j]>=a[i])
            {
                putchar('-');
                putchar('1');
                putchar(' ');
            }
        }
    }
    return 0;
}

打完暴力，想想有什么可以优化的地方。
这些数可以看做一个栈，每次输入的数是 \(a_i\)，然后就把栈内元素一个一个弹出，直到找到第一个小于 \(a_i\) 的数，然后把它输出，如果栈空了还没有答案，就输出 -1 。

那怎么优化呢？

可以发现，如果序列中存在 \(x<y\) 且 \(a_x≥a_y\) 那么 \(a_x\) 就永远不可能输出了，那么可以删掉 \(a_x\) 。
因此只要满足 \(栈顶≥a_i\) 就可以删去栈顶。
每次干完这些，查询第一个 \(≤a_i\) 的元素时仅需输出栈顶就行了。

这就是单调栈。相信你也明白了：它的单调指顺序单调。

代码

#include <bits/stdc++.h>
#define ll long long
#define rll register ll
#define cll const ll
#define N 100005
using namespace std;
inline ll read()
{
    rll x=0;bool f=1;static char c=getchar();
    while(!isdigit(c)){if(c=='-') f=0;c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    return f?x:-x;
}
inline void write(ll x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+48);
}//卡常
ll n=read(),top,stk[N];
int main()
{
    while(n--)
    {
        ll x=read();
        while(top&&stk[top]>=x) top--;
        if(top) write(stk[top]),putchar(' ');
        else putchar('-'),putchar('1'),putchar(' ');
        stk[++top]=x;
    }
    return 0;
}

单调队列

单调栈和单调队列都是思维难度比较大的数据结构，但只要想明白了就会觉得很简单。
要理解单调队列，首先得明白“单调”是指它存储的内容单调，而不是指它简单。

模板题（AcWing.154）

题目描述

给定一个大小为 \(n≤10^6\) 的数组。
有一个大小为 \(k\) 的滑动窗口，它从数组的最左边移动到最右边。
请输出滑动窗口位于每个位置时，窗口中的最大值和最小值。

样例

in:

8 3
1 3 -1 -3 5 3 6 7

out:

-1 -3 -3 -3 3 3
3 3 5 5 6 7

单调队列实现

思路

先看题目给的表：

窗口位置	最小值	最大值
[1 3 -1] -3 5 3 6 7	-1	3
1 [3 -1 -3] 5 3 6 7	-3	3
1 3 [-1 -3 5] 3 6 7	-3	5
1 3 -1 [-3 5 3] 6 7	-3	5
1 3 -1 -3 [5 3 6] 7	3	6
1 3 -1 -3 5 [3 6 7]	3	7

首先考虑用暴力怎么做，一定要先思考一下暴力！不然很难理解单调队列！因为它就是优化后的暴力。

先计算最小值。

这些数可以看做是一个队列，队头是 \(l\) ，队尾是 \(r\) ，每次滑动窗口，都是 \(l+1\) ， \(r+1\) 。查询则是 \(\operatorname{O(k)}\) 的遍历，这里就不放代码了。

显然很多窗口中都有一些我们肯定不需要的数。考虑优化。

可以发现，在如果队列中存在 \(x<y\) 且 \(a_x≥a_y\) ，那么 \(a_x\) 就没用了。因为只要 \(a_y\) 在队列中，\(a_x\) 就永远不可能输出，而且 \(a_y\) 在 \(a_x\) 后面，会比 \(a_x\) 的出栈时间晚（通俗点讲就是 \(a_y\) 比 \(a_x\) 活得久）。

这样一来，这个序列就成了单调递减的了，每次查询输出右端点 \(a_r\) 就行了。

计算最大值同理。

用单调队列维护后会得到单调递增的一个队列，每次查询也是输出右端点 \(a_r\) 。

代码

#include <bits/stdc++.h>
#define ll long long
#define rll register ll
#define cll const ll
#define N 1000005
using namespace std;
inline ll read()
{
    rll x=0;bool f=1;static char c=getchar();
    while(!isdigit(c)){if(c=='-') f=0;c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    return (f==1)?x:-x;
}
inline void write(ll x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+48);
}
ll n=read(),k=read(),l,r=-1,a[N],q[N];
int main()
{
    for(ll i=0;i<n;i++) a[i]=read();
    for(ll i=0;i<n;i++)
    {
        if(l<=r&&i-k+1>q[l]) l++;
        while(l<=r&&a[i]<=a[q[r]]) r--;
        q[++r]=i;
        if(i>=k-1) write(a[q[l]]),putchar(' ');
    }
    putchar('\n');l=0,r=-1;
    for(ll i=0;i<n;i++)
    {
        if(l<=r&&i-k+1>q[l]) l++;
        while(l<=r&&a[i]>=a[q[r]]) r--;
        q[++r]=i;
        if(i>=k-1) write(a[q[l]]),putchar(' ');
    }
    return 0;
}

trie 字典树

trie树（字典树），又称单词查找树，是一种树形结构，哈希树的变种。

trie 以字符为索引建树，因此，查找时间不带 \(log\) ，而是由字符串长度决定。

满trie树（原创图）。

但这张图不足以说明 trie 是如何存字符串的，因此有了下面一段。

trie 如何存字符串

下面这张图说明了 trie 是如何存字符串的，其中，\(\color{red}\textbf{☆}\) 表示从树顶走到某个位置的唯一路径上的所有节点表示了一个字符串。(原创图)

trie 的用处

• 可以当 \(map\) 用，更快。
• 统计以 \(str\) 为前缀的字符串的数量。

当然还有更多，这里就不一一介绍了。

模板题（AcWing.835）

题目描述

维护一个字符串集合，支持两种操作：

1. I x 向集合中插入一个字符串 \(x\) 。
2. Q x 询问一个字符串在集合中出现了多少次。

对于每个询问指令 Q x ，都要输出一个整数作为结果，表示 \(x\) 在集合中出现的次数。

样例

in：

5
I abc
Q abc
Q ab
I ab
Q ab

out：

1
0
1

trie 实现

思路

插入

trie 的插入可总结为一句话在第 \(x\) 层查找有没有表示 \(str\) 的第 \(x\) 个字符的节点，如果没有，就创建新节点。其中， \(1<x<\) strlen(str) 。

维护 \(trie\) 数组存储子节点的位置，分支最多26条。故为 trie[N][26] ，相当于链表中的 next[N] 。如 trie[1][0]=2 表示 \(节点1\) 的一个值为a的子节点为 \(节点2\)。
维护 \(cnt\) 数组存储以某节点结尾的字符串个数，同时也起标记作用。故为 cnt[N] 。
变量 \(idx\) 表示当前用到的下标。

插入代码：

inline void insert(char ch[N])
{
    ll p=0;
    for(ll i=0;ch[i];i++)
    {
        ll c=ch[i]-97;
        if(!trie[p][c]) trie[p][c]=++idx;
        p=trie[p][c];
    }
    cnt[p]++;
}

查询

代码很好理解，不用写思路。

查询代码：

inline ll query(char ch[N])
{
    ll p=0;
    for(ll i=0;ch[i];i++)
    {
        ll c=ch[i]-97;
        if(!trie[p][c]) return 0;
        p=trie[p][c];
    }
    return cnt[p];
}

这就是 trie 的模板。

代码

#include <bits/stdc++.h>
#define ll long long
#define rll register ll
#define cll const ll
#define N 100005
using namespace std;
inline ll read()
{
    rll x=0;bool f=1;static char c=getchar();
    while(!isdigit(c)){if(c=='-') f=0;c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    return (f==1)?x:-x;
}
inline void write(ll x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+48);
}//卡常
ll n=read(),idx,trie[N][26],cnt[N];
inline void insert(char ch[N])
{
    rll p=0;
    for(rll i=0;ch[i];i++)
    {
        rll c=ch[i]-97;
        if(!trie[p][c]) trie[p][c]=++idx;
        p=trie[p][c];
    }
    cnt[p]++;
}//插入
inline ll query(char ch[N])
{
    rll p=0;
    for(rll i=0;ch[i];i++)
    {
        rll c=ch[i]-97;
        if(!trie[p][c]) return 0;
        p=trie[p][c];
    }
    return cnt[p];
}//查询
int main()
{
    while(n--)
    {
        char op,str[N];cin >> op >> str;
        //这里是用 cin，如果要用 scanf，就得改成 char op[2]
        if(op=='I') insert(str);
        else write(query(str)),putchar('\n');
    }
    return 0;
}

并查集

并查集，是一种树形数据结构，用于维护不相交的集合。

基本原理

每个集合用一棵树来表示，树根的编号就是整个集合的编号。
每个节点存储了它的父节点。

模板题（AcWing.836）

题目描述

一共有 n 个数，编号是 1∼n，最开始每个数各自在一个集合中。

现在要进行 m 个操作，操作共有两种：

1. M a b ，将编号为 \(a\) 和 \(b\) 的两个数所在的集合合并，如果两个数已经在同一个集合中，则忽略这个操作；
2. Q a b ，询问编号为 \(a\) 和 \(b\) 的两个数是否在同一个集合中；

样例

in：

4 5
M 1 2
M 3 4
Q 1 2
Q 1 3
Q 3 4

out：

Yes
No
Yes

并查集实现

思路

维护一个数组 \(p\) 来表示每个节点的父节点。

判断树根

显然，如果一个节点的父节点是它本身，那它就是根节点。

代码：

inline bool is_root(ll x)
{
    if(p[x]==x) return 1;
    else return 0;
}

这个在本题中用不着。

合并集合

可以发现，如果要将 \(a\) 并入 \(b\) （其实等同于将 \(b\) 并入 \(a\) ），仅需在 \(a\) 的根节点和 \(b\) 的根节点间加入一条边。（原创图）

Q：那如果题目数据特别毒瘤，不间断地合并很多集合怎么办？那不就被卡成 \(\operatorname{O(n)}\) 了吗？
A：路径压缩的 find() 只会跑一遍 \(\operatorname{O(n)}\) ，就会重新变为 \(\operatorname{O(1)}\) 。

代码：

p[find(a)]=find(b);

求 \(x\) 的集合编号

递归查找。

inline ll find(ll x)
{
    if(p[x]!=x) p[x]=find(p[x]);//不断查找父节点，直到找到根节点
    return p[x];
}

以上代码添加了路径压缩，也就是 p[x]=find(p[x]) 在找到父节点的同时顺带更新了 p[x] 的值。

图示（原创图）：

相当于你问你爸爸你的祖先是谁，你爸爸也不知道，爸爸就去问爷爷，然后你的爷爷也不知道，爷爷就去问你的太爷爷，你的太爷爷年纪太大了，啥也不记得，就去问你的祖先。

代码

#include <bits/stdc++.h>
#define ll long long
#define rll register ll
#define cll const ll
#define N 100005
using namespace std;
inline ll read()
{
    rll x=0;bool f=1;static char c=getchar();
    while(!isdigit(c)){if(c=='-') f=0;c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    return (f==1)?x:-x;
}
inline void write(ll x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+48);
}
ll n=read(),m=read(),p[N];
inline ll find(ll x)
{
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}
int main()
{
    for(ll i=1;i<=n;i++) p[i]=i;
    while(m--)
    {
        char op[2];ll a,b;
        scanf("%s%lld%lld",op,&a,&b);//这里用 read() 会死
        if(op[0]=='M') p[find(a)]=find(b);
        else
        {
            if(find(a)==find(b)) puts("Yes");
            else puts("No");
        }
    }
    return 0;
}

简介

比较模拟堆和 STL 的优先队列：

	模拟堆	优先队列
相同点	可以维护极值	可以维护极值
不同点 1	可以在任意位置随意插入或删除一个元素	只能在堆顶添加或删除元素
不同点 2	可以查找第 \(k\) 大的元素	只能查询堆顶
不同点 3	可以查找第 \(k\) 个元素是第几大	只能查询堆顶
不同点 4	快	慢

简而言之，优先队列 priority_queue 能干的事模拟堆都能干，但模拟堆能干的事优先队列不一定能干，而且模拟堆更快。不过优先队列也不是一无是处，它凭借代码短，不易出错（因为是 STL 自带的），深受人们的青睐。在大部分题目中，用优先队列就足够了，如堆优化的 \(dijkstra\) 算法。

模拟堆

前置：

1. 按位左移 \(<<\) ，等同乘上 2 的几次方， \(x<<k\) 等同于 \(x×2^k\) ，如 \(x<<1\) 等同于 \(x×2\) 。
2. 按位右移 \(>>\) ，等同乘上 2 的几次方， \(x>>k\) 等同于 \(x÷2^k\) ，如 \(x>>1\) 等同于 \(x÷2\) 。
3. 按位或 \(|\) ， \(x>>1|1\) 等同于 \(x×2+1\) 。

模板题1（AcWing.838）

题目描述

输入一个长度为 \(n\) 的整数数列，从小到大输出前 \(m\) 小的数。

样例

in：

5 3
4 5 1 3 2

out：

1 2 3

简单模拟堆实现

思路

模拟堆可以实现的操作：

1. 插入一个数 \(x\)
2. 输出当前集合中的极值
3. 删除当前集合中的极值
4. 删除修改第 \(k\) 个插入的数

在本题中，仅需考虑前三个操作，也就是优先队列能实现的操作，可以看做一个堆排序。

下图演绎了堆排序的过程。

可以发现，再排序的过程中，每插入一个元素，就先把它放到堆顶，然后与它的子节点比较，如果比子节点大（从小到大排序），就交换它和它的子节点，然后重复这个过程。这个就是 down() 操作，复杂度 \(\operatorname{O(log_2n)}\) ，用递归实现。

那如何建出堆呢？

这里有一种神奇的建堆方式（好像也不怎么神奇），就是用数组建堆。
具体地说，用 \(a\) 数组存储堆，则：

• 根节点是 \(a_1\) 。
• 节点 \(a_x\) 的左儿子是 \(a_{x<<1}\) ，右儿子是 \(a_{x<<1|1}\) 。
• 节点 \(a_x\) 的父节点是 \(a_{x>>1}\) 。（整形变量自动向下取整）

这种存储方式初看好像有点不靠谱，似乎会有重复，实则不然。

下图说明了数组如何存储堆（原创图）：

代码

#include <bits/stdc++.h>
#define ll long long
#define rll register ll
#define cll const ll
#define N 100005
using namespace std;
inline ll read()
{
    rll x=0;bool f=1;register char c=getchar();
    while(c<48||c>57){if(c=='-') f=0;c=getchar();}
    while(c>=48&&c<=57){x=x*10+(c^48);c=getchar();}
    return f?x:-x;
}
inline void write(ll x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+48);
}//卡常
cll n=read();
ll m=read(),len=n,a[N];//len 代表堆内元素个数
inline void down(ll u)
{
    ll t=u;
    if((u<<1)<=len&&a[u<<1]<a[t]) t=u<<1;
    if((u<<1|1)<=len&&a[u<<1|1]<a[t]) t=u<<1|1;
    if(u!=t) swap(a[u],a[t]),down(t);
}//比子节点大则往下掉
int main()
{
    for(rll i=1;i<=n;i++) a[i]=read();//读入时直接读入即可（反正是无序的）
    for(rll i=(n>>1);i;i--) down(i);//对每个点进行 down() 操作，仅需操作一半的元素
    while(m--)
    {
        write(a[1]),putchar(' ');
        a[1]=a[len--],down(1);
        //为了方便，每次输出堆顶后用堆尾替换堆顶，再跑一遍 down()
    }
    return 0;
}

模板题2（AcWing.839）

题目描述

维护一个集合，初始时集合为空，支持如下几种操作：

1. I x ，插入一个数 \(x\)
2. PM ，输出当前集合中的最小值
3. DM ，删除当前集合中的最小值（数据保证此时的最小值唯一）
4. D k ，删除第 \(k\) 个插入的数
5. C k x ，修改第 \(k\) 个插入的数，将其变为 \(x\)

现在要进行 \(n\) 次操作，对于所有第 2 个操作，输出当前集合的最小值。

样例

in：

8
I -10
PM
I -10
D 1
C 2 8
I 6
PM
DM

out：

-10
6

复杂模拟堆实现

思路

上一题完成了前三个操作，本题将完成所有五个操作。

本题需要维护一些元素：

• \(m\) 表示插入的次数。
• \(ph\) 数组主要用于帮助从 \(m\) 映射到下标 \(k\) ， \(ph_x=y\) 表示第 \(x\) 个插入的元素的下标是 \(y\) 。
• \(hp\) 数组用于查找 \(m\) ， \(hp_x=y\) 表示下标为 \(x\) 的元素是第 \(y\) 个插入的元素。

这样一来，每次交换堆的节点就得交换三个数组 \(ph\) 、 \(hp\) 和 \(a\) 的元素。

代码

#include <bits/stdc++.h>
#define ll long long
#define rll register ll
#define cll const ll
#define N 100005
using namespace std;
inline ll read()
{
    rll x=0;bool f=1;register char c=getchar();
    while(c<48||c>57){if(c=='-') f=0;c=getchar();}
    while(c>=48&&c<=57){x=x*10+(c^48);c=getchar();}
    return f?x:-x;
}
inline void write(ll x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+48);
}//卡常
ll n=read(),m,len,a[N],ph[N],hp[N];
inline void heap_swap(ll x,ll y)
{
    swap(ph[hp[x]],ph[hp[y]]);//ph 以 hp 的元素值为下标
    swap(hp[x],hp[y]);
    swap(a[x],a[y]);
}//交换 a、ph、hp 的元素
inline void down(ll u)
{
    ll t=u;
    if((u<<1)<=len&&a[u<<1]<a[t]) t=u<<1;
    if((u<<1|1)<=len&&a[u<<1|1]<a[t]) t=u<<1|1;
    if(u!=t) heap_swap(u,t),down(t);
}//比子节点大则往下掉
inline void up(ll u)
{
    while((u>>1)&&a[u>>1]>a[u])
    {
        heap_swap(u>>1,u);
        up(u>>1);
    }
}//如果比父节点小则往上移
int main()
{
    while(n--)
    {
        string op;cin >> op;//用 string + cin 比较方便
        if(op=="I")
        {
            cll x=read();
            a[++len]=x;//插入在堆尾
            ph[++m]=len,hp[len]=m;//更新 ph 和 hp，它们互相依赖
            up(len);//如果比父节点小则往上移
        }//插入
        else if(op=="PM") write(a[1]),putchar('\n');//查询堆顶
        else if(op=="DM") heap_swap(1,len--),down(1);//删除堆顶
        else if(op=="D")
        {
            cll k=read(),x=ph[k];//x 保存当前被删除结点的下标
            heap_swap(x,len--);//交换堆顶和堆尾，删除堆尾
            up(x),down(x);
        }//删除第 k 个插入的数
        else if(op=="C")
        {
            cll k=read(),x=read();
            a[ph[k]]=x;
            down(ph[k]),up(ph[k]);
            //这两个操作只有一个会被执行，如果比父节点小则往上移，比子节点大则往下掉
        }//修改第 k 个插入的数为 x
    }
    return 0;
}

树状数组

树状数组（Binary Indexed Tree，BIT），即二叉索引树，适用于一些区间修改操作。

树状数组和线段树可是亲兄弟了，但他俩毕竟还有一些区别：树状数组能有的操作，线段树一定有；线段树有的操作，树状数组不一定有。

树状数组和线段树的复杂度同级，单次操作都是 \(\operatorname{O(log_2n)}\)，但树状数组常数更小，速度比线段树快得多，代码简单清晰，因此，能用树状数组时要尽量用。

不过，树状数组不像线段树是那样要用biuld建出一棵树，它是用数组模拟树形结构。

图解

下图解释了一维树状数组的存储模式，\(A\) 数组负责存储元素真正的值，\(C\) 数组就是树状数组，负责管理 \(A\) 数组，c[i]出发的箭头指向其管理的元素。比如要进行区间求和操作，c[i]就表示它出发的箭头指向的所有元素之和。

这就是树状数组的存储方式。

重点——lowbit函数

\(C_1=A_1\)
\(C_2=A_1+A_2\)
\(C_3=A_3\)
\(C_4=A_1+A_2+A_3+A_4\)
\(C_5=A_5\)
\(C_6=A_5+A_6\)
\(C_7=A_7\)
\(C_8=A_1+A_2+A_3+A_4+A_5+A_6+A_7+A_8\)
......

可以发现，这颗树是有规律的

设k为i的二进制中从最低位到高位连续零的长度，有：
\(C_i=A(i-2^k+1)+A(i-2^k+2)+...+A_i\)

求和：根据上面的式子，可得：
\(sum_i=C_i+C+C[(i-2^{k1})-2^{k2}]+...\)
\(sum_i=2^k\)

可得：

\(2^k=i\)&\(i^{i-1}\)
\(2^k=i\)&\(-i\)

这就是 lowbit 函数，它可以找到 \(x\) 在二进制上的第一个 1 的位置，证明不是很好理解，最好尽量理解证明，理解不了的暂且理解它的用处和用法就可以了。

lowbit函数代码

int lowbit(int x){return x & -x;}

如何在 \(C\) 数组中更新 \(A\) 数组的元素

树状数组的重点就是利用二进制的变化，动态地更新树状数组。

下图解释了树状数组的元素更新原理。

由图可知，a[i]如果要更新，那么首先管理它的直接上级c[i]就需要最先更新，然后利用lowbit找到c[i]的父节点并更新，直到更新完所有的节点。

区间加法代码

void add(ll x,ll y)
{
    while(x<=n)
    {
        c[x]+=y;
        x+=lowbit(x);
    }
}

如何建出树状数组

如果你看懂了上面的内容，再稍加思考，就可以想到。

其实只要在输入时将a[i]更新进去即可。

初始化代码

for(ll i=1;i<=n;i++)
{
    a[i]=read();
    add(i,a[i]);
}

如何查询区间和

请看下面一个例子：

如果你有几张钱币，分别是 1、2、4、8 元，那么你就可以凑出十五元以内的任何钱数，如：

\(1=1\)
\(2=2\)
\(3=2+1\)
\(4=4\)
\(5=4+1\)
\(6=4+2\)
\(7=4+2+1\)
\(8=8\)
\(9=8+1\)
\(10=8+2\)
\(11=8+2+1\)
\(12=8+4\)
\(13=8+4+1\)
\(14=8+4+2\)
\(15=8+4+2+1\)

同样的，利用 \(C\) 数组的不同组合，也可以求出任何的区间和。

区间求和的顺序与区间更新有点区别，区间更新的顺序是通过子节点一级级更新祖先，区间查询是从后往前用lowbit找到要加的元素。
首先定义一个 \(ret\) 来存储区间和。
然后用lowbit找到要加的元素并加上它。

区间求和代码

ll sum(ll x)
{
    ll ret=0;
    while(x)
    {
        ret+=c[x];
        x-=lowbit(x);
    }
    return ret;
}

区间求和完整程序

【模板】树状数组1（luogu.P3374）

#include <bits/stdc++.h>
#define ll long long
#define rll register ll
#define cll const ll
#define N 500005
using namespace std;
inline ll read()
{
    rll x=0;bool f=1;static char c=getchar();
    while(!isdigit(c)){if(c=='-') f=0;c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    return f?x:-x;
}
inline void write(ll x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+48);
}//卡常
cll n=read();
ll m=read(),c[N];
void add(ll i,ll x){while(i<=n) c[i]+=x,i+=(i&-i);}
ll answer(ll x)
{
    rll ret=0;
    while(x) ret+=c[x],x-=(x&-x);
    return ret;
}//树状数组
int main()
{
    for(rll i=1;i<=n;i++) add(i,read());
    while(m--)
    {
        cll op=read(),l=read(),r=read();
        if(op==1) add(l,r);
        else write(answer(r)-answer(l-1)),putchar('\n');
    }
    return 0;
}

标签：trie,ll,read,while,数据结构,节点,define
From： https://www.cnblogs.com/wangxuzhou-blog/p/17066813.html