4.4学习总结

一.线段树概念

一.定义:

线段树是一种二叉搜索树，而二叉搜索树，首先满足二叉树，即每个结点最多有两颗子树，并且是一颗搜索树，我们要知道，线段树的每个结点都存储了一个区间，也可以理解成一个线段，而搜索，就是在这些线段上进行搜索操作得到你想要的答案。

(线段树的适用范围很广，可以在线维护修改以及查询区间上的最值，求和。对于线段树来说，每次更新以及查询的时间复杂度为O(logN))

二.线段树操作思路

线段树主要是把一段大区间平均地划分成两段小区间进行维护，再用小区间的值来更新大区间。这样既能保证正确性，又能使时间保持在 log ⁡ 级别（因为这棵线段树是平衡的）。也就是说一个[L,R]区间会被划分为两个区间分别是[L,(L+R)/2]和[(L+R)/2+1,R]这两个小区间。然后再递归下去分直达L=R。

二.线段树具体操作

一.建树

建树时每次递归就要先判断l是否等于r,等于就说明是叶子节点,也就是区间是[l,l],直接赋值成a[l]/a[r]，再返回。否则就递归构造左儿子结点和递归构造右儿子结点,最后更新父节点。

void build(ll p,ll l,ll r)
{
	ll tl = p * 2, tr = p * 2 + 1;
	tree[p] = { l,r,ans[l],0 };
	if (l == r)
		return;
	ll mid = (l + r) / 2;
	build(tl, l, mid);
	build(tr, mid + 1, r);
	pushup(p);
}

二.区间修改

1.如果当前区间完全被覆盖在目标区间里将这个区间sum数组的的位置加上（r-l+1)*C

2.如果没有完全覆盖则先下传懒标记

3.如果这个区间的左孩子和目标区间有交集，那么就递归给左孩子分配任务

4.如果这个区间的右孩子和目标区间有交集，则递归分配任务给右孩子。

懒标记:(即在需要使用的时候在取值,否则存在父亲处)

//向上更新总和
void pushup(ll p)
{
	ll tl = p * 2, tr = p * 2 + 1;
	tree[p].sum = tree[tl].sum + tree[tr].sum;
}
//向下更新懒标记
void pushdown(ll p)
{
	ll tl = p * 2, tr = p * 2 + 1;
	if (tree[p].add)
	{
		tree[tl].sum += (tree[tl].r - tree[tl].l + 1) * tree[p].add;
		tree[tr].sum += (tree[tr].r - tree[tr].l + 1) * tree[p].add;
		tree[tl].add += tree[p].add;
		tree[tr].add += tree[p].add;
		tree[p].add = 0;
	}
}
//区间修改
void update(ll p,ll x,ll y,ll k)
{
	ll tl = p * 2, tr = p * 2 + 1;
	if (x <= tree[p].l && tree[p].r <= y) {
		tree[p].sum += (tree[p].r - tree[p].l + 1) * k;
		tree[p].add += k;
		return;
	}
	ll mid = (tree[p].l + tree[p].r) / 2;
	pushdown(p);
	if (x <= mid)
		update(tl, x, y, k);
	if (y > mid)
		update(tr, x, y, k);
	pushup(p);
}

三.区间查询

1.如果当前区间完全被覆盖在目标区间里将对于sum位置的数据返回

2.如果没有完全覆盖则先下传懒标记

3.如果这个区间的左孩子和目标区间有交集，那么就递归给左孩子分配任务

4.如果这个区间的右孩子和目标区间有交集，则递归分配任务给右孩子。

ll query(ll p, ll x, ll y)
{
	ll tl = p * 2, tr = p * 2 + 1;
	if (x <= tree[p].l && tree[p].r <= y)
		return tree[p].sum;
	ll mid = (tree[p].l+tree[p].r) / 2;
	pushdown(p);
	ll sum = 0;
	if (x <= mid)
		sum += query(tl, x, y);
	if (y > mid)
		sum += query(tr, x, y);
	return sum;
}

三.例题分析

线段树的模版题,熟练掌握区间修改和区间查询即可,注意数据范围,要开long long

#include<iostream>
#include <stdio.h>
#include<set>
#include<map>
#include<string>
#include<cstring>
#include<math.h>
#include<algorithm>
#include<vector>
using namespace std;
#define N 1000005
typedef long long ll;
int n, m, cnt;
int ans[N];
struct node {
	ll l, r, sum, add;
}tree[N*4];

void pushup(ll p)
{
	ll tl = p * 2, tr = p * 2 + 1;
	tree[p].sum = tree[tl].sum + tree[tr].sum;
}

void pushdown(ll p)
{
	ll tl = p * 2, tr = p * 2 + 1;
	if (tree[p].add)
	{
		tree[tl].sum += (tree[tl].r - tree[tl].l + 1) * tree[p].add;
		tree[tr].sum += (tree[tr].r - tree[tr].l + 1) * tree[p].add;
		tree[tl].add += tree[p].add;
		tree[tr].add += tree[p].add;
		tree[p].add = 0;
	}
}

void build(ll p,ll l,ll r)
{
	ll tl = p * 2, tr = p * 2 + 1;
	tree[p] = { l,r,ans[l],0 };
	if (l == r)
		return;
	ll mid = (l + r) / 2;
	build(tl, l, mid);
	build(tr, mid + 1, r);
	pushup(p);
}

ll query(ll p, ll x, ll y)
{
	ll tl = p * 2, tr = p * 2 + 1;
	if (x <= tree[p].l && tree[p].r <= y)
		return tree[p].sum;
	ll mid = (tree[p].l+tree[p].r) / 2;
	pushdown(p);
	ll sum = 0;
	if (x <= mid)
		sum += query(tl, x, y);
	if (y > mid)
		sum += query(tr, x, y);
	return sum;
}

void update(ll p,ll x,ll y,ll k)
{
	ll tl = p * 2, tr = p * 2 + 1;
	if (x <= tree[p].l && tree[p].r <= y) {
		tree[p].sum += (tree[p].r - tree[p].l + 1) * k;
		tree[p].add += k;
		return;
	}
	ll mid = (tree[p].l + tree[p].r) / 2;
	pushdown(p);
	if (x <= mid)
		update(tl, x, y, k);
	if (y > mid)
		update(tr, x, y, k);
	pushup(p);
}
int main()
{
	scanf("%lld%lld", &n, &m);
	for (int i = 1; i <= n; i++)
		scanf("%lld", &ans[i]);
	build(1, 1, n);
	while (m--)
	{
		char s;
		ll choice, x, y, z;
		cin >> s;
		if (s == 'C') {
			scanf("%lld%lld%lld", &x, &y, &z);
			update(1,x,y,z);
		}
		if (s == 'Q') {
			scanf("%lld%lld", &x, &y);
			printf("%lld\n", query(1, x, y));
		}
	}
	return 0;
}

二.JDBC学习

刚开始接触mysql和JDBC的知识,初步学习其相关特点

实例演示

import java.sql.Connection;
import java.sql.DriverManager;
import java.sql.Statement;

public class jdbc {
    public static void main(String[] args) throws Exception {
        //1.注册驱动
        Class.forName("com.mysql.cj.jdbc.Driver");

        //2.获取连接
        String upl="jdbc:mysql://localhost:3306/chat";
        String username="root";
        String password="wei1810335767";
        Connection conn= DriverManager.getConnection(upl,username,password);

        //3.定义sql
        String sql="update user set sex='k' where id=1";

        //4.获取执行sql对象Statement
        Statement stat = conn.createStatement();

        //5.执行sql
        int i = stat.executeUpdate(sql);

        //6.处理结果
        System.out.println(i);

        //7.释放资源
        stat.close();
        conn.close();
    }
}