差分数组｜AcWing 797. 差分｜ AcWing 798. 差分矩阵

797. 差分

差分理论：

package main
 
import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)
 
var scanner *bufio.Scanner
 
func insert(l int, r int, c int, b []int) {
	b[l] += c
	b[r+1] -= c
}
func main() {
	//假设数组从1开始赋值
	var n, m int
	var a, b []int
	scanner = bufio.NewScanner(os.Stdin)
	//用例一行有十万个数据 bufio.NewScanner的底层buf数组最大缓存限制为64K，要重新分配内存
	bs := make([]byte, 2000*1024)
	scanner.Buffer(bs, len(bs))
	//读取一行
	scanner.Scan()
	line := strings.Split(scanner.Text(), " ")
	n, _ = strconv.Atoi(line[0])
	m, _ = strconv.Atoi(line[1])
	//赋值n+2为了构造差分数组不越界
	a = make([]int, n+2)
	b = make([]int, n+2)
	//读取一行
	scanner.Scan()
	line = strings.Split(scanner.Text(), " ")
	for i, s := range line {
		x, _ := strconv.Atoi(s)
		a[i+1] = x
	}
	//相当于构造b[i]=a[i]-a[i-1]，即构建差分数组
	for i := 1; i <= n; i++ {
		// insert(i, i, a[i], b) 这个有点难理解，按照下面那个好理解些, 已经是理解了，可以带入几个值就知道了。注意a数组和b数组的定义。
		b[i] = a[i] - a[i-1]
	}
	for i := 0; i < m; i++ {
		scanner.Scan()
		line := strings.Split(scanner.Text(), " ")
		l, _ := strconv.Atoi(line[0])
		r, _ := strconv.Atoi(line[1])
		c, _ := strconv.Atoi(line[2])
		insert(l, r, c, b)
	}
	for i := 1; i <= n; i++ {
		a[i] = a[i-1] + b[i]
	}
	for i := 1; i <= n; i++ {
		fmt.Printf("%d ", a[i])
	}
}
 
 
 
// 第一次构建差分数组，用insert那个，是这样的
牢记：
a[i]是b[i]的前缀和
b[i]是a[i]的查分数组
什么意思呢？ 
就是说 a[i] = b[1] + b[2]+...+b[i]
如何构造的呢？正常是令b[1] = a[1], b[2] = a[2] - a[1], b[3] = a[3] - a[2], b[n] = a[n] - a[n-1]
 
 
 
b[1] += a[1] = a[1]
b[2] -= a[1] = -a[1]
 
 
b[2] += a[2] = -a[1] + a[2]  
b[3] -= a[2] = -a[2]
 
b[3] += a[3] = -a[2] + a[3] = a[3] - a[2] # 这里
....
....
b[n] = a[n] - a[n-1]
 
 
 
// 我们想要的查分数组b是下面这样的
b[1] = a[1] 
b[2] = a[2] - a[1]
b[3] = a[3] - a[2]	# 这里
b[n] = a[n] - a[n-1]
 
a[n] = b[1] + b[2] + ... + b[n]

798. 差分矩阵

 

 

 

package main
 
import (
    "bufio"
    "fmt"
    "os"
    "strconv"
    "strings"
)
const n = 1005
var a, b [n][n]int
func main() {
 
    var n, m, q, x1, x2, y1, y2, c int
 
    fmt.Scan(&n, &m, &q)
    scanner := bufio.NewScanner(os.Stdin)
    bs := make([]byte, 2000*1024)
    scanner.Buffer(bs,len(bs))
    for i := 1; i<=n; i++ {
        scanner.Scan()
        temp := strings.Split(scanner.Text()," ")
        for j := 1; j <= m; j ++ {
            a[i][j], _ = strconv.Atoi(temp[j-1])
            insert(i,j,i,j,a[i][j])
 
        }
    }
    for i := 1; i<= q; i++{
        scanner.Scan()
        temp := strings.Split(scanner.Text()," ")
        x1,_ = strconv.Atoi(temp[0])
        y1,_ = strconv.Atoi(temp[1])
        x2,_ = strconv.Atoi(temp[2])
        y2,_ = strconv.Atoi(temp[3])
        c,_ = strconv.Atoi(temp[4])
        insert(x1,y1,x2,y2,c)
 
    }
    for i := 1; i<= n; i++{
        res := make([]string, m)
        for j := 1; j<=m; j++ {
            b[i][j] += b[i-1][j] + b[i][j-1] - b[i-1][j-1]
            res[j-1] = strconv.Itoa(b[i][j])
        }
        fmt.Println(strings.Join(res," "))
    }
}
func insert(x1,y1,x2,y2,c int)  {
    b[x1][y1] += c
    b[x1][y2+1] -= c
    b[x2+1][y1] -= c
    b[x2+1][y2+1] += c
}