0%

要解决的问题

  • 通过什么方式实现上下文的切换,并且方便测量时间。
  • 如何保证在具有多个CPU的系统中,保证上下文切换的进程处于同一个处理器上

上下文切换的方式

利用两个管道,测量在父子进程之间互相切换的时间成本,具体流程见下图

[管道的介绍](Linux管道通信 | SnowDawn’Home)

3

​ 使用双管道在父子进程之间相互切换

  1. 父进程向管道Pi1 写入获取到的开始时的时间,使用gettimeofday()函数
  2. 父进程从Pi2 读取,但是此时的Pi2 中还没有内容写入,所以父进程陷入等待,系统切换到子进程
  3. 子进程从Pi1 中读取开始的时间,并且记录此时的时间,与开始的时间相减,输出切换的时间
  4. 子进程向Pi2 中写入开始时间,此时切换到等待读取的子进程,再次算出一个切换时间

使切换进程保证在同一个处理器上

使用sched_seaffinity()调用实现,该函数的参数比较复杂,这里只是简单的使用,没有详细的研究与介绍。

测量程序代码(标明在注释中)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#define _GNU_SOURCE
#include <sched.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/wait.h>
#include <sys/time.h>

#define errExit(msg) \
do \
{ \
perror(msg); \
exit(EXIT_FAILURE); \
} while (0)

int main()
{
cpu_set_t set; // cpu_set_t是一个用来存放CPU的集合的结构体
int parentCPU, childCPU; //
parentCPU = 0;
childCPU = 0; //设置父进程和子进程的CPU核心

CPU_ZERO(&set); //将CPU核心集合清零
int pi1[2]; //父进程和子进程的管道
int pi2[2];
char buf1[30], buf2[30]; //父进程和子进程的管道缓冲区
int p1 = pipe(pi1); //创建父进程和子进程的管道
int p2 = pipe(pi2);
long temptime;
struct timeval start, end; //记录时间
int i;
if (p1 < 0 || p2 < 0) //判断管道是否创建成功
errExit("pipe");
int rc = fork(); //创建子进程
for (i = 0; i < 10; ++i) //循环测试十次
{
if (rc < 0) //判断子进程是否创建成功
{
fprintf(stderr, "fork failed");
exit(1);
}
else if (rc == 0)
{
CPU_SET(childCPU, &set); //将子进程的CPU核心设置为childCPU
if (sched_setaffinity(getpid(), sizeof(set), &set) == -1)
errExit("sched_setaffinity"); //设置CPU核心
read(pi1[0], buf1, 25); //读取父进程的数据
gettimeofday(&end, NULL); //获取结束时间
printf("%d\n", end.tv_usec - atol(buf1)); //输出时间差
gettimeofday(&start, NULL); //获取开始时间
sprintf(buf2, "%ld", start.tv_usec); //将开始时间转换为字符串
write(pi2[1], buf2, 25); // 将开始时间写入管道
}
else
{
CPU_SET(parentCPU, &set); //将父进程的CPU核心设置为parentCPU
if (sched_setaffinity(getpid(), sizeof(set), &set) == -1)
errExit("sched_setaffinity"); //设置CPU核心
gettimeofday(&start, NULL); //获取开始时间
sprintf(buf1, "%ld", start.tv_usec); //将开始时间转换为字符串
write(pi1[1], buf1, 25); // 将开始时间写入管道
read(pi2[0], buf2, 25); // 读取子进程的数据
gettimeofday(&end, NULL); //获取结束时间
printf("%d\n", end.tv_usec - atol(buf2)); //输出时间差
}
}
return 0;
}

测试程序的运行结果如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
90
15
6
7
5
6
5
6
5
6
5
7
5
6
5
6
5
7
5
398

对测试结果的分析

在十次循环的测量中,开始的一次和最后的一次测量时间较长,具体为何会出现这样的情况有以下猜测:

  • 对于刚创建的子进程,还未进入到系统的缓存,进程之间的切换较慢。
  • 对于最后一次测量上下文切换时间,待解决,择日向老师请教。

另,此测试程序得到的结果并不只是上下文切换的时间,还包括对读和写的系统调用,将字符串转化为数字,设置cpu亲和度的调用等时间,根据之前对系统调用的测量,并且忽略其他细小的时间消耗,该系统的上下文切换时间应该在 4 – 5 微秒。

什么是管道

​ 管道, 英文名 pipe 。

​ 在系统操作和执行命令的时候,通常需要将一个程序的输出交给另外一个程序处理,这样的操作虽然可以使用输入输出重定向加文件实现,但是比较麻烦。

​ 管道的概念就是这样诞生,将两个进程的输入和输出通过一个管道相连,以便达到进程之间相互通信的目的。

​ 从本质上来说,管道就是一个文件,前面的的进程以写的方式打开文件,后面的程序以读的方式打开文件,利用这样的方式实现进程间通信。

​ 虽然实现形态上是文件,但是管道本身并不占用磁盘或者其他外部存储的空间。在Linux的实现上,它占用的是内存空间。所以,Linux上的管道就是一个操作方式为文件的内存缓冲区。


管道的分类

  • 匿名管道

  • 命名管道

    匿名管道只能在父进程和子进程之间使用,在父进程产生子进程之前,打开一个管道文件,然后再fork()

产生一个子进程,由于父子进程共享文件描述符,所以可以通过这个管道文件相互通信。

匿名管道的调用原型:

1
2
#include <unistd.h>
int pipe(int pipefd[2]);

大致执行示意图如下实现了半双工通信

半双工通信

一个最简单的管道系统编程代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <stdlib.h>
#include <stdio.h>
#include <unistd.h>
#include <string.h>
#include <sys/types.h>
#include <sys/wait.h>

#define STRING "hello world!"

int main()
{
int pipefd[2]; //为pipe准备文件标识符
pid_t pid;
char buf[BUFSIZ];

if (pipe(pipefd) == -1) { //使用pipe()系统调用
perror("pipe()");
exit(1);
}

pid = fork(); //创建子进程
if (pid == -1) {
perror("fork()");
exit(1);
}

if (pid == 0) {
/* this is child. */
printf("Child pid is: %d\n", getpid());
if (read(pipefd[0], buf, BUFSIZ) < 0) { //子进程读管道中父进程写入的信息
perror("write()"); //没有读到的话就是写出现了问题
exit(1);
}

printf("%s\n", buf); //将从父进程得到的信息打印

bzero(buf, BUFSIZ); //将buf清零
//将要送给parent的信息写入buf中
snprintf(buf, BUFSIZ, "Message from child: My pid is: %d", getpid());
//调用pipe()的写入实现
if (write(pipefd[1], buf, strlen(buf)) < 0) {
perror("write()");
exit(1);
}

} else {
/* this is parent */
printf("Parent pid is: %d\n", getpid());
//将要送给子进程的信息写入buf
snprintf(buf, BUFSIZ, "Message from parent: My pid is: %d", getpid());
//调用pipe()的写入实现
if (write(pipefd[1], buf, strlen(buf)) < 0) {
perror("write()");
exit(1);
}

sleep(1); //父进程写入完成以后,等待子进程完成读取

bzero(buf, BUFSIZ);
//读取管道中子进程写入的信息
if (read(pipefd[0], buf, BUFSIZ) < 0) {
perror("write()");
exit(1);
}

printf("%s\n", buf);

wait(NULL);
}


exit(0);
}

​ 程序运行效果如下,父进程先给子进程发一个消息,子进程读到消息后将消息打印,然后再给父进程发消息,父进程读到消息后打印从子进程收到的消息。

一般来说不使用父子进程之间的半双工通信,管道的推荐使用方法是单工模式,即一个进程只写入管道,一个进程只读入管道 ,不需要使用的标识符就将其关闭。

单工

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <stdlib.h>
#include <stdio.h>
#include <unistd.h>
#include <string.h>
#include <sys/types.h>
#include <sys/wait.h>

#define STRING "hello world!"

int main()
{
int pipefd[2];
pid_t pid;
char buf[BUFSIZ];

if (pipe(pipefd) == -1) {
perror("pipe()");
exit(1);
}

pid = fork();
if (pid == -1) {
perror("fork()");
exit(1);
}

if (pid == 0) {
/* this is child. */
close(pipefd[1]); //子进程只读,所以关闭写入

printf("Child pid is: %d\n", getpid());
if (read(pipefd[0], buf, BUFSIZ) < 0) {
perror("write()");
exit(1);
}

printf("%s\n", buf);

} else {
/* this is parent */
close(pipefd[0]);//父进程只写入,所以关闭读

printf("Parent pid is: %d\n", getpid());

snprintf(buf, BUFSIZ, "Message from parent: My pid is: %d", getpid());
if (write(pipefd[1], buf, strlen(buf)) < 0) {
perror("write()");
exit(1);
}

wait(NULL);
}
exit(0);

​ 命名管道不仅可以在父子进程中实现消息的传递,通过命名可以实现任意进程之间的管道通信,此篇博客不再详细介绍命名管道。

测量成本的工具

使用 gettimeofday() 这个典型时钟函数来测量时间成本,返回自1970-01-01 00:00:00到现在所经历的秒数,调用两次该函数通过相减的方式获取时间差。

根据函数的定义:此函数在sys/time.h>

1
int gettimeofday(struct timeval *, struct timezone *);

定义了两个结构体,分别记录时间和时区

1
2
3
4
5
6
7
8
9
struct timeval {undefined
time_t tv_sec;
suseconds_t tv_usec;
};//存储秒和微秒

struct timezone {undefined
int tz_minuteswest;
int tz_dsttime;
};//记录时区

使用举例 : 测试其时间精度是否可以达到定义中声明的微秒级别

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int main()
{
struct timeval start,end;
int i = 10;
gettimeofday(&start, NULL);
for(i=0;i<10;++i) {
gettimeofday(&start, NULL);
gettimeofday(&end, NULL);
printf("%ld\n", end.tv_usec - start.tv_usec);
printf("%ld %ld\n", end.tv_usec, start.tv_usec);
}
gettimeofday(&end, NULL);
return 0;
}

这是在空系统调用测试中连续调用 gettimeofday()函数,如果精确度可以达到微秒 级别,那么两次连续调用获取的时间相减应该近似于0

执行结果如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
0
157238 157238
0
157275 157275
0
157278 157278
1
157282 157281
0
157285 157285
0
157288 157288
0
157291 157291
1
157295 157294
0
157298 157298
0
157301 157301

基本可以确定在微秒级别

注意

一般情况下,系统调用的时间成本是在 ns的级别,所以即使可以达到微秒级别,也要通过多次测量取平均值的办法才可以尽可能的实现准确。


测量系统调用的时间成本

这里使用简单的 read() 函数来测量调用的成本 , 测试程序的代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <stdio.h>
#include <sys/time.h>
#include <unistd.h>
#include <fcntl.h>
#include <stdlib.h>

int main()
{
int n = 10;
while (n--)
{
int fd = open("./6.2.c", O_RDONLY);
int i;
char buf[10];
struct timeval start, end;
if (fd == -1)
{
fprintf(stderr, "file open failed!\n");
exit(1);
}
gettimeofday(&start, NULL);
for (i = 0; i < 10000; ++i)
{
read(fd, buf, 0); //为了让程序结束,把read的第二个参数改为0,这样就可以尽可能测量纯粹的系统调用耗时
}
gettimeofday(&end, NULL);
printf("%d :万次的平均结果: %lf\n", 10 - n, (1000000 * (end.tv_sec - start.tv_sec) + end.tv_usec - start.tv_usec) * 1.0 / 10000); //强制转换为double
close(fd);
}
return 0;
}

测试程序的结果如下

1
2
3
4
5
6
7
8
9
10
1 :万次的平均结果: 0.583100
2 :万次的平均结果: 0.598400
3 :万次的平均结果: 0.594100
4 :万次的平均结果: 0.595600
5 :万次的平均结果: 0.601000
6 :万次的平均结果: 0.615700
7 :万次的平均结果: 0.606900
8 :万次的平均结果: 0.589100
9 :万次的平均结果: 0.595500
10 :万次的平均结果: 0.584900

从多次运行万次平均结果看,对于 read 函数,系统调用的时间约为 0. 6 微秒。

单调栈

即栈内的元素是有某种单调性的。

用于求特定问题的解。

作用情景

[求一个数列的每个数的左边第一个比它小的数字](830. 单调栈 - AcWing题库)

要求左边第一个比它小的数,那么在之前每一个数入栈的时候就进行判断,只将满足递减单调性的数据存入,其余的弹出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>

using namespace std;

const int N = 100010;

int stk[N], tt;

int main()
{
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
int x;
scanf("%d", &x);
//如果栈是非空的,且栈顶元素不比要入栈的元素小,将栈顶弹出,以形成单调栈
while (tt && stk[tt] >= x)
tt--;
//形成单调栈以后的栈顶就是要找的第一个比要入栈元素小的值
if (tt)
printf("%d ", stk[tt]);
else
printf("-1 ");
//最后将这个元素入栈
stk[++tt] = x;
}
return 0;
}

优先队列

与单调栈的定义类似,优先队列里的元素是按照某种单调性排列的。

使用优先队列可以简化特定要求的与队列有关的问题。

作用情景

[滑动窗口](154. 滑动窗口 - AcWing题库)

一组数据

给定一个大小为 k的窗口,从数组的头开始滑动,窗口里最多只能同时存在k个数。

求每次滑动时,窗口里的最大值和最小值。

与优先队列的处理方式类似,只将满足单调性的元素从队尾入队,不满足的 从队尾出队

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>

using namespace std;

const int N = 1000010;

int n, k;
//a[N]数组中存储要处理的数组,q[N]数组中存储队列里的数在a[N]数组里的下标
int a[N], q[N];

int main()
{
scanf("%d%d", &n, &k);
for (int i = 0; i < n; i++)
scanf("%d", &a[i]);
//定义队头和队尾
int hh = 0, tt = -1;
for (int i = 0; i < n; i++)
{
//使用 i - k + 1 来控制队列(滑动窗口)中的元素数量,每当队列中的元素超出k, 就把队头元素出队
if (hh <= tt && q[tt] - k + 1 > q[hh])
hh++;
//要入队的元素要比队列中的所有元素都要大
while (hh <= tt && a[q[tt]] >= a[i])
tt--;
q[++tt] = i;
if (i >= k - 1)
//队头的元素永远是最小的
printf("%d ", a[q[hh]]);
}
printf("\n");
//找最大值与最小值方法一样,改变入队的限制即可
hh = 0, tt = -1;
for (int i = 0; i < n; i++)
{
if (hh <= tt && i - k + 1 > q[hh])
hh++;
//要入队的元素要比队列中的所有元素都小
while (hh <= tt && a[q[tt]] <= a[i])
tt--;
q[++tt] = i;
if (i >= k - 1)
printf("%d ", a[q[hh]]); //输出队头的最大元素
}
return 0;
}

总结

单调栈和优先队列的使用是为了满足特定集中情况下的算法需求,应用的场景比较有限

通常的使用场景是:

某个问题使用到了栈和队列的结构,但是朴素算法的遍历的复杂度太高,单调栈和优先队列可以优化栈和队列,使其具有一定的单调性,降低解决这些问题的复杂度。

队列

一个线性表,在一端放入数据,在另一端弹出数据,先放入的数据先弹出。

与链表的实现方式基本相同

数组模拟的队列的基本操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <iostream>

using namespace std;

const int N = 100010;

//将tail设为-1 , 这样在插入了一个数的时候,队头head 就是 tail 队列长度是1
int queue[N], head, tail = -1;

//在队尾插入元素,在队头弹出元素

void push(int x)
{
queue[++tail] = x;
}

string ifempty()
{
if (head > tail)
return "YES";
else
return "NO";
}

void pop()
{
//指针移动,队头的元素相当于被切掉了
head++;
}

int query()
{
return queue[head];
}

int main()
{
int m;
cin >> m;
string op;
while (m--)
{
cin >> op;
if (op == "push")
{
int x;
cin >> x;
push(x);
}
else if (op == "pop")
{
pop();
}
else if (op == "empty")
{
cout << ifempty() << endl;
}
else
cout << query() << endl;
}
return 0;
}

只能从一头进出的线性表

最后被放入的必须最先被取出

数组模拟栈的基本操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <iostream>

using namespace std;

const int N = 100010;

int stk[N], k;

void push(int x)
{
stk[++k] = x;
}

string ifempty()
{
if (k <= 0)
return "YES";
else
return "NO";
}

void pop()
{
k--;
}

int query()
{
return stk[k];
}

int main()
{
int m;
cin >> m;
string op;
while (m--)
{
cin >> op;
if (op == "push")
{
int x;
cin >> x;
push(x);
}
else if (op == "pop")
{
pop();
}
else if (op == "empty")
{
cout << ifempty() << endl;
}
else
cout << query() << endl;
}
return 0;
}

挺简单的,随便记录一下。

双链表

与单链表相比,区别是:
双链表的每一个节点都有对应的前驱和后继。

可以完成一些单链表无法完成的任务。

[基础的双链表操作](827. 双链表 - AcWing题库)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <iostream>

using namespace std;

const int N = 100010;

int e[N], l[N], r[N], idx;

void init()
{
//将0 , 1 分别设为头节点和尾部节点
l[1] = 0;
r[0] = 1;
idx = 2;
}

//向插入的第k个数后面插入一个数
//也可以通过将参数k 改为l[k]来实现向k的左边插入一个数
void add(int k, int x)
{
e[idx] = x;
l[idx] = k;
r[idx] = r[k];
l[r[k]] = idx;
r[k] = idx;
idx++;
}

//移去第k个插入的数
void remove(int k)
{
r[l[k]] = r[k];
l[r[k]] = l[k];
}

int main()
{
init();
int m;
cin >> m;
string op;
while (m--)
{
cin >> op;
if (op == "L")
{
//向头节点的后面添加一个数,就是在最前面加上一个数
int x;
cin >> x;
add(0, x);
}
else if (op == "R")
{
//向尾节点前面一个数的后面加一个数,就是在最后加上一个数
int x;
cin >> x;
add(l[1], x);
}
else if (op == "D")
{
//删去第k个插入的数
int x;
cin >> x;
remove(x + 1);
//第一个插入的数的下标是2 ,因为将 1 定义为了末尾
}
else if (op == "IL")
{
//在第k个插入的数前面插入一个数
int k, x;
cin >> k >> x;
add(l[k + 1], x);
//在第k个左边的右面插入,就是在k的左边插入
}
else
{
int k, x;
cin >> k >> x;
add(k + 1, x);
}
}
for (int i = r[0]; i != 1; i = r[i])
cout << e[i] << " ";
return 0;
}

数组模拟单链表(静态链表)

链表

数据对象的存储结构可以分为两种:0顺序存储结构和链式存储结构

顺序存储结构要求所有的元素依次存放在一片连续的存储空间中

链式存储结构无需占用一整块存储空间,但是为了表示节点之间的关系,需要给每一个节点附加指针字段,用于存放后继元素的存储地址。

单链表的数组模拟实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <iostream>

using namespace std;

const int N = 100010;

//e[N] : 当前节点的值
//ne[N] : 当前节点指向的下一个节点下标
//head :头节点指向的节点的下标
//idx :当前插入了几个 ,也就是最新节点的插入次序
int e[N], ne[N], head, idx;

//整个结构的初始化
void init()
{
//head 开始时指向空,表示为-1
head = -1;
//已经插入了零个数据
idx = 0;
}
//向头节点后面插入数据
void add_to_head(int x)
{
e[idx] = x;
ne[idx] = head;
head = idx;
idx++;
}

//向第k个插入的数据后面插入一个数据
void add(int k, int x)
{
e[idx] = x;
ne[idx] = ne[k];
ne[k] = idx;
idx++;
}

//移除第k个插入的数据后面的一个数据
void remove(int k)
{
ne[k] = ne[ne[k]];
}

int main()
{
init();
int m;
cin >> m;
while (m--)
{
int x, k;
char op;
cin >> op;
if (op == 'H')
{
cin >> x;
add_to_head(x);
}
else if (op == 'D')
{
cin >> k;
// k为0的时候的特判
if (k == 0)
head = ne[head];
//下表是从0开始的,所有第k个的下标是k - 1
remove(k - 1);
}
else
{
cin >> k >> x;
add(k - 1, x);
}
}
for (int i = head; i != -1; i = ne[i])
cout << e[i] << ' ';

return 0;
}

单链表的局限性

单链表不能在链表的任意位置插入一个数据,因为单链表只能找到某一个数据的后继,而不能找到一个数据的前导。

要解决这一个问题,要使用到双链表。

概念

在一个很大的范围内 , 只有 很小的数据容量。

使用离散化,将这些数据 存储在从 1 开始的数组里 , 再进行后续的处理。


处理方法

  • 将输入的 值存入动态数组 vector
  • 将所有的值排序
  • 储存进数组的值相当于坐标 , 所以要进行去重的操作,方便后续的使用和处理。
  • 编写一个find()函数,用于找到原数据对应的离散化之后的数据位置(动态数组中的位置)
  • 根据题目的逻辑进行相应的 操作。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
vector<int> alls; // 存储所有待离散化的值
sort(alls.begin(), alls.end()); // 将所有值排序
alls.erase(unique(alls.begin(), alls.end()), alls.end()); // 去掉重复元素

// 二分求出x对应的离散化的值
int find(int x) // 找到第一个大于等于x的位置
{
int l = 0, r = alls.size() - 1;
while (l < r)
{
int mid = l + r >> 1;
if (alls[mid] >= x) r = mid;
else l = mid + 1;
}
return r + 1; // 映射到1, 2, ...n
}

模板例题

[求区间和](802. 区间和 - AcWing题库)

假定有一个无限长的数轴,数轴上每个坐标上的数都是 0。

现在,我们首先进行 n 次操作,每次操作将某一位置 xx 上的数加 c。

接下来,进行 m 次询问,每个询问包含两个整数 l 和 r,你需要求出在区间 [l ,r] 之间的所有数的和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

const int N = 300010; //数据范围限制,可能有 1e5 个add , 和 2e5 个坐标

int n, m;
int a[N], s[N]; //相应坐标的数据,和最后求和时使用的前缀和

vector<int> alls; //存储所有数据
vector<PII> add, query; //两个操作,使用pair<int,int>存储一次操作中的两个参数

int find(int x) //使用二分确定离散化后原数据位置的函数
{
int l = 0, r = alls.size() - 1;
while (l < r)
{
int mid = l + r >> 1;
if (alls[mid] >= x)
r = mid;
else
l = mid + 1;
}
return l + 1;
}

int main()
{
cin >> n >> m;
for (int i = 0; i < n; i++)
{
int x, c;
cin >> x >> c;
add.push_back({x, c}); //存储add操作
alls.push_back(x); //存储原数据
}

for (int i = 0; i < m; i++) //存储query操作
{
int l, r;
cin >> l >> r;
query.push_back({l, r});

alls.push_back(l); //存储询问的位置
alls.push_back(r);
}

sort(alls.begin(), alls.end()); //排序和去重操作
alls.erase(unique(alls.begin(), alls.end()), alls.end());

for (auto item : add) //处理add插入操作
{
int x = find(item.first); //获取原数据离散化的坐标
a[x] += item.second; //修改相应坐标上的值
}

for (int i = 1; i <= alls.size(); i++)
s[i] = s[i - 1] + a[i]; //处理前缀和

for (auto item : query) //处理query询问操作
{
int l, r;
l = find(item.first), r = find(item.second);//获取离散化后坐标
cout << s[r] - s[l - 1] << endl; //利用前缀和求值输出
}

return 0;
}

lowbit( )

作用: 获取一个二进制数的 最后一位 1 及以后的数

1
2
3
4
int lowbit()
{
return x & -x;
}

例题:[二进制中 1 的个数](801. 二进制中1的个数 - AcWing题库)

给定一个长度为 n的数列,请你求出数列中每个数的二进制表示中 1 的个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>

using namespace std;

int n ;

int lowbit( int x)
{
return x & -x; //实现方法:x 与运算 x 的取反
}

int main( )
{
cin >> n ;
for ( int i = 0 ; i < n ; i++)
{
int x ;
cin >> x ;
int res = 0 ;
while (x)
{
x -= lowbit(x); //把最后一位1 及以后的都减去
res ++ ; //计数加一
} //重复
cout << res << ' ' ;
}
return 0 ;
}

求n的第k位数字(二进制)

n >> k & 1