信息老师的前缀和

题目描述

运用前缀和思想进行数据预处理，能够避免数据的重复计算，且大大降低了算法的时间复杂度。这天，狐狸老师想考一考大家对前缀和的掌握情况，于是出了一道题：求a~b之间1出现的次数。

输入格式

共 n+1 行； 第一行，一个整数 n（1≤n≤105），表示查询次数。 接下来n行，每行包含两个整数 a 和 b （1≤a＜b≤105），数与数之间以一个空格隔开。

输出格式

n行，每行一个整数，分别表示每次循环时1出现的次数。

3
1 10
20 30
100 110

2
1
13

提示

（暂无提示）

来源

童程童美