前言

这是我的算法笔记系列帖子的第一篇文章，因为我走的是java开发方向但算法题都是c++写的，我个人觉得c++写题更方便，所以为了防止大家跟着我的帖子入门不方便，特在此写了这篇介绍c++常用函数和常用技巧的帖子。

本算法笔记系列帖子里包含的示例是全部完整的lc hot 100原题，后续会详细地分章节介绍链表，字符串，动态规划，图，前缀和等常考知识点及其常见套路模板，同时会给出大量例题，新手小白肯定能快速跟上篮子哥的节奏

这个专栏给的例题的解法我不追求达到最优解法，而是我借鉴了lc的大量解法，加上自己的理解注释，追求尽可能的满足套路模板的解法，让大家尽可能的更容易的接受和理解。

觉得本贴有用的话欢迎点赞收藏订阅关注和评论！

我把这系列算法笔记帖子放入了我的八股大全、算法、项目话术、面试话术全专栏：https://www.nowcoder.com/creation/manager/columnDetail/j8ZZk0

想要学习Java冲实习或冲春招的，我能助你一臂之力，我之前整理了高质量可速成的魔改外卖项目话术和7000字轮子项目话术，还有超全超精品八股大全专栏，怎么写简历，怎么包装实习经历，怎么0基础速成冲春招和实习等等等等精品帖子，大家可以去看看我的精品文章汇总帖子：https://www.nowcoder.com/discuss/721704696242536448?sourceSSR=users

1.基本函数

1.substr()

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

int main(){
    string s;
    cin>>s;
    string tmp = s.substr(1,2);//下标1开始2位长度子串
    cout<<tmp<<endl;
}
12345
23

2.字符串转整型stoi()

int main(){
    string s;
    cin>>s;
    int n = stoi(s);
    cout<<n;
}
12.7
输出12
12
输出12

3.字符串转整型stof()

int main() {
    string s;
    cin>>s;
    double d = stof(s);
    cout<<d;
}
"3.11"
3.11

4.数字转字符串to_string()

int n;
    cin>>n;
    string s;
    s += to_string(n);
    s+= "1";
    cout<<s;

5.lower_bound( )和upper_bound( )

lower_bound( )和upper_bound( )都是利用二分查找的方法在一个排好序的数组中进行查找的。

在从小到大的排序数组中，

lower_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

upper_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10;
const int INF=2*int(1e9)+10;
#define LL long long
int cmd(int a,int b){
	return a>b;
}
int main(){
	int num[6]={1,2,4,7,15,34}; 
	sort(num,num+6);                           //按从小到大排序 
	int pos1=lower_bound(num,num+6,7)-num;    //返回数组中第一个大于或等于被查数的值 
	int pos2=upper_bound(num,num+6,7)-num;    //返回数组中第一个大于被查数的值
	cout<<pos1<<" "<<num[pos1]<<endl;3 7
	cout<<pos2<<" "<<num[pos2]<<endl;4 15
	
} 

2.字符串根据","或' '划分

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

int main(){
    string s;
    getline(cin,s);//这样才可以输入带空格的字符串
    stringstream ss(s);
    int k = 0;
    vector<string> strs;
    string tmp;
    while(getline(ss, tmp, ',')){
        strs.push_back(tmp);
    }
    for(int i=0;i<strs.size();i++){
        cout<<strs[i]<<endl;
    }
    cout<<strs.size()<<endl;
}
a,b,c
a
b
c
3

3.浮点型4舍去5入的指定精度函数

情况1：要求一定要精确到小数点后2位
int a = 1,b = 3;
double num = a*1.0/b;
std::cout << std::fixed << std::setprecision(2) << num << std::endl;
输入1，输出1.00
输入2/3,输出0.67
输入1/3,输出0.33

//情况2：四舍五入最多保留2位小数
int a = 2,b=3;
double res = a*1.0/b;
cout<<round(res*100)/100;
输入1，输出1
输入2/3,输出0.67
输入1/3,输出0.33

4.数状数组

1.什么是树状数组？

顾名思义就是一个结构为树形结构的数组，于二叉树的结构类似但又不同，它是在二叉树的结构上删除了一些中间节点，来看两幅图就明白了.

1.这是二叉树的结构

2.这是树状数组的结构

不难发现，树状数组相比于二叉树删除了一些节点，但是为什么要删除呢？这就和树状数组的一些性质(lowbit)有关了，不懂没关系，继续往下看.

2.树状数组可以解决什么问题呢？

可以解决大部分区间上面的修改以及查询的问题，例如1.单点修改，单点查询，2.区间修改，单点查询，3.区间查询，区间修改，换言之，线段树能解决的问题，树状数组大部分也可以，但是并不一定都能解决，因为线段树的扩展性比树状数组要强.

3.树状数组和线段树的区别在哪？

有人会问了既然线段树的问题能够用树状数组解决而且线段树还比树状数组扩展性强，那为什么不直接用线段树呢？问的很好，树状数组的作用就是为了简化线段树，举个例子：一个问题可以用线段树解决写代码半个小时，但是用树状数组只需要10分钟，那么你会选择哪一个算法呢?没错，基于某些简单的问题，我们没必要用到功能性强

4.树状数组的优点

优点：修改和查询操作复杂度于线段树一样都是logN,但是常数比线段树小，并且实现比线段树简单

缺点：扩展性弱，线段树能解决的问题，树状数组不一定能解决.

5.lowbit(x)运算

6.问题引入

8.例题

1.单点修改，区间查询

如题，已知一个数列，你需要进行下面两种操作：

• 将某一个数加上 x
• 求出某区间每一个数的和

输入格式

第一行包含两个正整数 n,m，分别表示该数列数字的个数和操作的总个数。

第二行包含 n 个用空格分隔的整数，其中第 i 个数字表示数列第 i 项的初始值。

接下来 m 行每行包含 3 个整数，表示一个操作，具体如下：

• 1 x k 含义：将第 x 个数加上 k
• 2 x y 含义：输出区间 [x,y] 内每个数的和

输出格式

输出包含若干行整数，即为所有操作 2 的结果。

输入输出样例

输入 #1复制

5 5
1 5 4 2 3
1 1 3
2 2 5
1 3 -1
1 4 2
2 1 4

输出 #1复制

14
16

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
int n,m,tree[2000010]; // 定义全局变量n、m和数组tree
int lowbit(int k) // 定义lowbit函数，用于获取k的二进制表示中最低位的1的位置
{
    return k & -k;
}
void add(int x,int k) // 定义add函数，用于将k加到tree数组的第x个元素上，并更新后续元素的值
{
    while(x<=n)
    {
        tree[x]+=k;
        x+=lowbit(x);
    }
}
int sum(int x) // 定义sum函数，用于计算tree数组中前x个元素的和
{
    int ans=0;
    while(x!=0)
    {
        ans+=tree[x];
        x-=lowbit(x);
    }
    return ans;
}
int main() // 主函数
{
    cin>>n>>m; // 输入n和m的值
    for(int i=1;i<=n;i++) // 循环读取n个数，并将它们加到tree数组中
    {
        int a;
        scanf("%d",&a);
        add(i,a);
    }
    for(int i=1;i<=m;i++) // 循环处理m次操作
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c); // 输入操作类型a和操作范围b、c
        if(a==1) // 如果操作类型为1，则将c加到tree数组的第b个元素上，并更新后续元素的值
            add(b,c);
        if(a==2) // 如果操作类型为2，则输出tree数组中第b个元素到第c个元素的和
            cout<<sum(c)-sum(b-1)<<endl;
    }
}

2.区间修改，单点查询

题目描述

如题，已知一个数列，你需要进行下面两种操作：

1. 将某区间每一个数加上 x；
2. 求出某一个数的值。

输入格式

第一行包含两个整数 N、M，分别表示该数列数字的个数和操作的总个数。

第二行包含 N* 个用空格分隔的整数，其中第 i* 个数字表示数列第 i* 项的初始值。

接下来 M 行每行包含 2或 4个整数，表示一个操作，具体如下：

操作 11： 格式：1 x y k 含义：将区间 [x,y] 内每个数加上 k*；

操作 22： 格式：2 x 含义：输出第 x* 个数的值。

输出格式

输出包含若干行整数，即为所有操作 2 的结果。

输入输出样例

输入 #1复制

5 5
1 5 4 2 3
1 2 4 2
2 3
1 1 5 -1
1 3 5 7
2 4

输出 #1复制

6
10

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
using namespace std;
int n,m; // 定义两个整数变量n和m
int input[500010]; // 定义一个长度为500010的整数数组input
int tree[500100]; // 定义一个长度为500100的整数数组tree
int lowbit(int x) // 定义一个函数lowbit，输入一个整数x，返回x的二进制表示中最低位的1所对应的值
{
    return x & -x;
}
void add(int x,int k) // 定义一个函数add，输入两个整数x和k，将k累加到tree数组中下标为x及之后的节点的值上
{
    while(x<=n)
    {
        tree[x]+=k;
        x+=lowbit(x);
    }
}
int search(int x) // 定义一个函数search，输入一个整数x，返回tree数组中下标为x及其祖先节点的值的和
{
    int ans=0;
    while(x!=0)
    {
        ans+=tree[x];
        x-=lowbit(x);
    }
    return ans;
}
int main() // 主函数
{
    cin>>n>>m; // 输入两个整数n和m
    for(int i=1;i<=n;i++) // 循环读取n个整数并存入input数组
        cin>>input[i];
    for(int i=1;i<=m;i++) // 循环m次
    {
        int a;
        scanf("%d",&a); // 读取一个整数a
        if(a==1) // 如果a等于1
        {
            int x,y,z;
            scanf("%d%d%d",&x,&y,&z); // 读取三个整数x、y和z
            add(x,z); // 调用add函数，将z累加到tree数组中下标为x及其祖先节点的值上
            add(y+1,-z); // 调用add函数，将-z累加到tree数组中下标为y+1及其祖先节点的值上
        }
        if(a==2) // 如果a等于2
        {
            int x;
            scanf("%d",&x); // 读取一个整数x
            printf("%d\n",input[x]+search(x)); // 输出input数组中下标为x的值与tree数组中下标为x及其祖先节点的值的和
        }
    }
}

3.树状数组求逆序对

题目描述

猫猫 TOM 和小老鼠 JERRY 最近又较量上了，但是毕竟都是成年人，他们已经不喜欢再玩那种你追我赶的游戏，现在他们喜欢玩统计。

最近，TOM 老猫查阅到一个人类称之为“逆序对”的东西，这东西是这样定义的：对于给定的一段正整数序列，逆序对就是序列中 ��>��a**i>a**j 且 �<�i<j 的有序对。知道这概念后，他们就比赛谁先算出给定的一段正整数序列中逆序对的数目。注意序列中可能有重复数字。

Update:数据已加强。

输入格式

第一行，一个数 �n，表示序列中有 �n个数。

第二行 �n 个数，表示给定的序列。序列中每个数字不超过 109109。

输出格式

输出序列中逆序对的数目。

输入输出样例

输入 #1复制

6
5 4 2 6 3 1

输出 #1复制

11

分析:对于原序列，比当前位置数大的数前出现在序列中，就会构成逆序对,例如：5 3 2 1，5,3,2比1先出现且都比1大，那么此时就构成了3个逆序对数,那么我们可以对以及出现的数字进行标记，枚举序列中每一个位置的数，统计有多少比它大的数字以及出现，然后累加进答案即可,这就是一个单点修改+区间查询的操作，树状数组实现,不过需要注意的是这道题数字很大，需要离散化存储.

注意：这道题自定义排序参数cmp的实现，不能单纯的a.val<b.val,如果相等的话也要保证位置不变,不然贡献会增多，想想为什么？
#include<bits/stdc++.h>
using namespace std;
const int Maxn = 5e5+10;
int t[Maxn]={0};//树状数组
typedef struct node{
   int val,ind;
}Node;
Node stu[Maxn];
int Rank[Maxn];
typedef long long ll;
int n;
int lowbit(int x){return x&(-x);}
/*单点修