Session一致性
Session一致性 session: 服务器为每个用户创建一个会话的,存储用户相关的信息,以便多次请求能够定位到同一个上下文。 web开发中,web-server可以自动为同一个浏览器的访问自动创建session,提供数据存储功能,比如会把用户的登录信息存储在session中,以保持登录状态。…
线段树不是一棵完全二叉树,因为区间可能不能完全平分,但线段树是一棵平衡二叉树
对一棵满二叉树,h层,一共有2^h-1个节点,对于h-1层,有2^(h-1)个节点,最后一层的节点数比前面所有层节点数之和多一
即如果区间有n个元素的话,最多需要4n的空间就可以全部放下(做了较大的富裕),且线段树不考虑添加元素,区间是固定的,我们使用4n的静态空间就可以了
SegmentTree
package com.liuyao;
/**
* @author liuyao
* @date 2018/07/28
*/
public class SegmentTree<E> {
private E[] tree;
private E[] data;
private Merger<E> merger;
public SegmentTree(E[] arr, Merger<E> merger) {
this.merger = merger;
data = (E[]) new Object[arr.length];
for (int i = 0; i < arr.length; i++) {
data[i] = arr[i];
}
tree = (E[]) new Object[4 * arr.length];
buildSegmentTree(0, 0, arr.length - 1);
}
/**
* 构造线段树
*
* @param treeIndex
* @param l
* @param r
*/
private void buildSegmentTree(int treeIndex, int l, int r) {
// 递归截止条件,最后只左右相等,将当前的元素赋给tree[treeIndex]
if (l == r) {
tree[treeIndex] = data[l];
return;
}
int leftTreeIndex = leftChild(treeIndex);
int rightTreeIndex = rightChild(treeIndex);
int mid = l + (r - l) / 2;
buildSegmentTree(leftTreeIndex, l, mid);
buildSegmentTree(rightTreeIndex, mid + 1, r);
tree[treeIndex] = merger.merge(tree[leftTreeIndex], tree[rightTreeIndex]);
}
/**
* 获得数组中的元素个数
*
* @return
*/
public int getSize() {
return data.length;
}
/**
* 根据索引返回相应的数组中的值
*
* @param index 索引
* @return
*/
public E get(int index) {
if (index < 0 || index >= data.length) {
throw new IllegalArgumentException("Index is illegal");
}
return data[index];
}
/**
* 返回一棵完全二叉树的数组表示中,一个索引所表示的元素的左孩子节点的索引
*
* @param index
* @return
*/
public int leftChild(int index) {
return 2 * index + 1;
}
/**
* 返回一棵完全二叉树的数组表示中,一个索引所表示的元素的右孩子节点的索引
*
* @param index
* @return
*/
public int rightChild(int index) {
return 2 * index + 2;
}
/**
* 返回区间[queryL,queryR]的值
*
* @param queryL
* @param queryR
* @return
*/
public E query(int queryL, int queryR) {
if (queryL < 0 || queryL >= data.length || queryR < 0 || queryR >= data.length || queryL > queryR) {
throw new IllegalArgumentException("Index is illegal");
}
return query(0, 0, data.length - 1, queryL, queryR);
}
/**
* 在以treeIndex为根的线段树中[l...r]的范围里,搜索区间[query...queryR]的值
*
* @param treeIndex
* @param l
* @param r
* @param queryL
* @param queryR
* @return
*/
private E query(int treeIndex, int l, int r, int queryL, int queryR) {
if (l == queryL && r == queryR) {
return tree[treeIndex];
}
int mid = l + (r - l) / 2;
// 找到以treeIndex为根左右两个孩子的索引
int leftTreeIndex = leftChild(treeIndex);
int rightTreeIndex = rightChild(treeIndex);
if (queryL >= mid + 1) {
return query(rightTreeIndex, mid + 1, r, queryL, queryR);
} else if (queryR <= mid) {
return query(leftTreeIndex, l, mid, queryL, queryR);
}
E leftResult = query(leftTreeIndex, l, mid, queryL, mid);
E rightResult = query(rightTreeIndex, mid + 1, r, mid + 1, queryR);
return merger.merge(leftResult, rightResult);
}
/**
* 将index位置的值,更新为e
* @param index
* @param e
*/
public void set(int index,E e){
if (index < 0 || index >= data.length){
throw new IllegalArgumentException("Index is illegal");
}
data[index]=e;
set(0,0,data.length-1,index,e);
}
/**
* 在以treeIndex为根的线段树中更新index的值为e
* @param treeIndex
* @param l
* @param r
* @param index
* @param e
*/
private void set(int treeIndex,int l,int r,int index,E e){
if (l == r){
tree[treeIndex]=e;
return;
}
int mid=l+(r-l)/2;
int leftTreeIndex=leftChild(treeIndex);
int rightTreeIndex=rightChild(treeIndex);
if (index >= mid+1){
set(rightTreeIndex,mid+1,r,index,e);
}else {
set(leftTreeIndex,l,mid,index,e);
}
tree[treeIndex]=merger.merge(tree[leftTreeIndex],tree[rightTreeIndex]);
}
@Override
public String toString() {
StringBuilder res = new StringBuilder();
res.append('[');
for (int i = 0; i < tree.length; i++) {
if (tree[i] != null) {
res.append(tree[i]);
} else {
res.append("null");
}
if (i != tree.length - 1) {
res.append(", ");
}
}
res.append(']');
return res.toString();
}
}
Merger
package com.liuyao;
/**
* @author liuyao
* @date 2018/07/28
*/
public interface Merger<E> {
public E merge(E a, E b);
}
Main
package com.liuyao;
public class Main {
public static void main(String[] args) {
Integer[] nums = {-2, 0, 3, -5, 2, -1};
// SegmentTree<Integer> segTree = new SegmentTree<>(nums,
// new Merger<Integer>() {
// @Override
// public Integer merge(Integer a, Integer b) {
// return a + b;
// }
// });
SegmentTree<Integer> segTree = new SegmentTree<>(nums,
(a, b) -> a + b);
System.out.println(segTree);
System.out.println(segTree.query(2,5));
}
}
Session一致性 session: 服务器为每个用户创建一个会话的,存储用户相关的信息,以便多次请求能够定位到同一个上下文。 web开发中,web-server可以自动为同一个浏览器的访问自动创建session,提供数据存储功能,比如会把用户的登录信息存储在session中,以保持登录状态。…
深入学习Java线程池 先来看一下大体的架构: 先从最开始的开始吧,我们平时提交的任务都是 Runnable 类型的,可以看到 Executor 里面的 execute…